Geodesic
$L(p,q)$-labeling of graphs with interval representations
Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 4, pp. 1215-1235 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

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},
     year = {2023},
     volume = {43},
     number = {4},
     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
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
%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/

[1] A.A. Bertossi, C.M. Pinotti and R.B. Tan, Efficient use of radio spectrum in wireless networks with channel separation between close stations, in: DIALM '00: Proceedings of the 4th International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications, (ACM, New York 2000) 18–27. https://doi.org/10.1145/345848.345853

[2] H.L. Bodlaender, T. Kloks, R.B. Tan and J. van Leeuwen, Approximations for \lambda-colorings of graphs, Comput. J. 47 (2004) 193–204. https://doi.org/10.1093/comjnl/47.2.193

[3] D.E. Brown, Variations on Interval Graphs, Ph.D. Thesis (University of Colorado Denver, 2004).

[4] D.E. Brown, B.M. Flesch and L.J. Langley, Interval k-graphs and orders, Order 35 (2018) 495–514. https://doi.org/10.1007/s11083-017-9445-0

[5] D.E. Brown, S.C. Flink and J.R. Lundgren, Interval k-graphs, Congr. Numer. 156 (2002) 79–93.

[6] T. Calamoneri, The {L}(h, k)-labelling problem: An updated survey and annotated bibliography, Comput. J. 54 (2011) 1344–1371. https://doi.org/10.1093/comjnl/bxr037

[7] T. Calamoneri, S. Caminiti, R. Petreschi, S. Olariu, On the {L}(h, k)-labeling of co-comparability graphs and circular-arc graphs, Networks 53 (2009) 27–34. https://doi.org/10.1002/net.20257

[8] M.R. Cerioli and D.F.D. Posner, On {L}(2,1)-coloring split, chordal bipartite, and weakly chordal graphs, Discrete Appl. Math. 160 (2012) 2655–2661. https://doi.org/10.1016/j.dam.2012.03.018

[9] G.J. Chang and D. Kuo, The {L}(2,1)-labeling problem on graphs, SIAM J. Discrete Math. 9 (1996) 309–316. https://doi.org/10.1137/S0895480193245339

[10] G.J. Chang, W.-T. Ke, D. Kuo, D.D.-F. Liu and R.K. Yeh, On L(d,1)-labelings of graphs, Discrete Math. 220 (2000) 57–66. https://doi.org/10.1016/S0012-365X(99)00400-8

[11] Y. Civan, Z. Deniz and M.A. Yetim, Bounding the chromatic number of squares of {K}4-minor-free graphs, Discrete Math. 342 (2019) 1894–1903. https://doi.org/10.1016/j.disc.2019.03.011

[12] D.J. Decock and B.M. Flesch, Asteroidal-triple-free interval k-graphs, Australas. J. Combin. 74 (2019) 227–238.

[13] D. Gonçalves, On the {L}(p,1)-labelling of graphs, Discrete Math. 308 (2008) 1405–1414. https://doi.org/10.1016/j.disc.2007.07.075

[14] J.R. Griggs and R.Y. Yeh, Labelling graphs with a condition at distance 2, SIAM J. Discrete Math. 5 (1992) 586–595. https://doi.org/10.1137/0405048

[15] F. Havet, B. Reed and J.-S. Sereni, {L}(2,1)-labelling of graphs, in: SODA '08: Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms (2008) 621–630.

[16] Y.-Z. Huang, C.-Y Chiang, L.-H. Huang and H.-G Yeh, On {L}(2,1)-labeling of generalized Petersen graphs, J. Comb. Optim. 24 (2012) 266–279. https://doi.org/10.1007/s10878-011-9380-8

[17] J.-H. Kang, {L}(2,1)-labeling of Hamiltonian graphs with maximum degree 3, SIAM J. Discrete Math. 22 (2008) 213–230. https://doi.org/10.1137/050632609

[18] N.V.R. Mahadev and U.N. Peled, Threshold Graphs and Related Topics (Elsevier, North Holland, 1995).

[19] B.S. Panda and P. Goel, {L}(2,1)-labeling of perfect elimination bipartite graphs, Discrete Appl. Math. 159 (2011) 1878–1888. https://doi.org/10.1016/j.dam.2010.07.008

[20] B.S. Panda and P. Goel, {L}(2,1)-labeling of dually chordal graphs and strongly orderable graphs, Inform. Process. Lett. 112 (2012) 552–556. https://doi.org/10.1016/j.ipl.2012.04.003

[21] S. Paul, M. Pal and A. Pal, {L}(2,1)-labeling of permutation and bipartite permutation graphs, Math. Comput. Sci. 9 (2015) 113–123. https://doi.org/10.1007/s11786-014-0180-2

[22] D. Sakai, Labeling chordal graphs: distance two condition, SIAM J. Discrete Math. 7 (1994) 133–140. https://doi.org/10.1137/S0895480191223178

[23] W.T. Trotter, Combinatorics and Partially Ordered Sets: Dimension Theory (Johns Hopkins University Press, Baltimore, 2001).