L(p,q)-labeling of graphs with interval representations


Yetim M. A.

DISCUSSIONES MATHEMATICAE GRAPH THEORY, pp.1-21, 2021 (Journal Indexed in SCI Expanded)

  • Publication Type: Article / Article
  • Publication Date: 2021
  • Doi Number: 10.7151/dmgt.2426
  • Title of Journal : DISCUSSIONES MATHEMATICAE GRAPH THEORY
  • Page Numbers: pp.1-21

Abstract

We provide upper bounds on the L(p,q)-labeling number of graphs which have interval (or circular-arc) representations via simple greedy algorithms. We prove that there exists an L(p,q)-labeling with span at most max{2(p+q-1)Δ-4q+2, (2p-1)μ+(2q-1)Δ- 2q+1} for interval k-graphs, max{p,q}Δ for interval graphs, 3max{p,q}Δ+p for circular-arc graphs, 2(p+q-1)Δ-2q+1 for permutation graphs and (2p-1)Δ+(2q-1)(μ-1) for cointerval graphs. In particular, these improve existing bounds on L(p,q)-labeling of interval graphs and L(2,1)-labeling of permutation graphs. Furthermore, we provide upper bounds on the coloring of the squares of aforementioned classes.