L(p,q)-Labeling of Graphs with Interval Representations

09/12/2019

∙

by   Mehmet Akif Yetim, et al.

∙

0

∙

share

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, max{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 and circular arc graphs and L(2,1)-labeling of permutation graphs. Furthermore, we provide upper bounds on the coloring of the squares of aforementioned classes.