Article in volume
Authors:
Title:
$L(p,q)$-labeling of graphs with interval representations
PDFSource:
Discussiones Mathematicae Graph Theory 43(4) (2023) 1215-1235
Received: 2020-09-20 , Revised: 2021-07-12 , Accepted: 2021-07-12 , Available online: 2021-07-31 , https://doi.org/10.7151/dmgt.2426
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 a span at most
$\max\{2(p+q-1)\Delta-4q+2, (2p-1)\mu+(2q-1)\Delta-2q+1\}$ for interval
$k$-graphs, $\max\{p,q\}\Delta$ for interval graphs, $3\max\{p,q\}\Delta+p$
for circular-arc graphs, $2(p+q-1)\Delta-2q+1$ for permutation graphs and
$(2p-1)\Delta+(2q-1)(\mu-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
References:
- 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 - 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 - D.E. Brown, Variations on Interval Graphs, Ph.D. Thesis (University of Colorado Denver, 2004).
- 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 - D.E. Brown, S.C. Flink and J.R. Lundgren, Interval $k$-graphs, Congr. Numer. 156 (2002) 79–93.
- 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 - 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 - 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 - 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 - 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 - 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 - D.J. Decock and B.M. Flesch, Asteroidal-triple-free interval $k$-graphs, Australas. J. Combin. 74 (2019) 227–238.
- 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 - 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 - 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.
- 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 - 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 - N.V.R. Mahadev and U.N. Peled, Threshold Graphs and Related Topics (Elsevier, North Holland, 1995).
- 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 - 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 - 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 - D. Sakai, Labeling chordal graphs: distance two condition, SIAM J. Discrete Math. 7 (1994) 133–140.
https://doi.org/10.1137/S0895480191223178 - W.T. Trotter, Combinatorics and Partially Ordered Sets: Dimension Theory (Johns Hopkins University Press, Baltimore, 2001).
Close