Geodesic
$L(p,q)$-labeling of graphs with interval representations
Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 4, pp. 1215-1235

Voir la notice de l'article provenant de la source Library of Science

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 a 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.
Keywords: $L(p,q)$-labeling, channel assignment, interval representation, square graph, interval graph, interval $k$-graph, permutation graph, circular-arc graph, cointerval graph, interval order, chromatic number 
@article{DMGT_2023_43_4_a18,
     author = {Yetim, Mehmet Akif},
     title = {$L(p,q)$-labeling of graphs with interval representations},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {1215--1235},
     publisher = {mathdoc},
     volume = {43},
     number = {4},
     year = {2023},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2023_43_4_a18/}
}
TY  - JOUR
AU  - Yetim, Mehmet Akif
TI  - $L(p,q)$-labeling of graphs with interval representations
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2023
SP  - 1215
EP  - 1235
VL  - 43
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2023_43_4_a18/
LA  - en
ID  - DMGT_2023_43_4_a18
ER  - 
%0 Journal Article
%A Yetim, Mehmet Akif
%T $L(p,q)$-labeling of graphs with interval representations
%J Discussiones Mathematicae. Graph Theory
%D 2023
%P 1215-1235
%V 43
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2023_43_4_a18/
%G en
%F DMGT_2023_43_4_a18
Yetim, Mehmet Akif. $L(p,q)$-labeling of graphs with interval representations. Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 4, pp. 1215-1235. http://geodesic.mathdoc.fr/item/DMGT_2023_43_4_a18/