Abstract
G has a list k-L(2, 1)-labeling if for any k-list assignment L, there exists a coloring \(c:V(G)\rightarrow \bigcup \limits _{v\in V} L(v)\) of G such that \(c(v)\in L(v)\) for \(\forall v\in V(G)\) and for \(\forall u,v\in V(G)\), \(|c(u)-c(v)|\ge 2\) if \(d(u,v)=1\), \(|c(u)-c(v)|\ge 1\) if \(d(u,v)=2\). \(\lambda _{2,1}^{l}(G)=\min \{k|G\) has a list k-L(2, 1)-labeling\(\}\) is called the list L(2, 1)-labeling number of G. In this paper, we prove that for planar graph with maximum degree \(\Delta \ge 5\), girth \(g\ge 13\) and without adjacent 13-cycles, \(\lambda _{2,1}^{l}(G)\le \Delta +3\) holds. Moreover, the upper bound \(\Delta +3\) is tight.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Alon N (1999) Combinatorial nullstellensatz. Comb Probab Comput 8:7–29
Bella P, Král D, Mohar B, Quittnerová K (2007) Labeling planar graphs with a condition at distance two. Eur J Comb 28:2201–2239
Borodin O, Broersma HJ, Glebov A, van den Heuvel J (2002) Stars and bunches in planar graphs. Part II: general planar graphs and colourings, CDAM research report series 2002–05
Chang GJ, Kuo D (1996) The \(L(2,1)\)-labeling problem on graphs. SIAM J Disc Math 9:309–316
Dvořák Z, Král D, Nejedlý P, Škrekovski R (2008) Coloring squares of planar graphs with girth six. European J. Combin. 29 (4): 838–849.
Fiala J, Škrekovski R (2005) Generalized list T–colorings of cycles. Discrete Appl. Math. 148 (1):13–25
Gonçalves D (2008) On the \(L(p,1)\)-labelling of graphs. Disc Math 308(8):1405–1414
Griggs JR, Yeh RK (1992) Labeling graphs with a condition at distance 2. SIAM J Disc Math 5:586–595
Hale WK (1980) Frequency assignment: theory and applications. Proc IEEE 68(12):1497–1514
Havet F, Reed B, Sereni JS (2012) Griggs and Yeh’s conjecture and L(p,1) –labellings. SIAM J Discrete Math 26(1):145–168
Huo JJ, Wang WF, Xu CD (2017) Neighbor sum distinguishing index of subcubic graphs. Graphs Comb 33:419–431
Král D, Škrekovski R (2003) A theorem about channel assignment problem. SIAM J Disc Math 16(3):426–437
Molloy M, Salavatipour MR (2005) A bound on the chromatic number of the square of a planar graph. J Comb Theory Ser B 94(2): 189–213
Van den Heuvel J, McGuinness S (2003) Coloring of the square of a planar graph. J Graph Theory 42:110–124
Wang WF (2006) The L(2,1)-labelling of trees. Disc Appl Math 154:598–603
Wang WF, Cai LZ (2008) Labelling planar graphs without 4-cycles with a conditionon distance two. Disc Appl Math 156:2241–2249
Wang WF, Lih KW (2003) Labeling planar graphs with conditions on girth and distance two. SIAM J Disc Math 17:264–275
Zhu HY, Lv XZ, Wang CQ, Chen M (2012) Labelling planar graphs without 4,5-cycles with a condition on distance two. SIAM J Disc Math 26:52–64
Zhu HY, Hou LF, Chen W, Lv XZ (2014) The \(L(p, q)\)-labelling of planar graphs without 4-cycles. Disc Appl Math 162:355–363
Zhu HY, Miao LY, Chen S, Lv XZ, Song WY (2018) The list \(L(2,1)\)-labeling of planar graphs. Disc Math 341:2211–2219
Zhu HY, Gu Y, Sheng JJ, Lv XZ (2018) List 2-distance \(\Delta +3\)-coloring of planar graphs without 4,5-cycles. J Comb Optim 36:1411–1424
Zhu JL, Bu YH, Pardalos MP, Du HW, Wang HJ, Liu B (2018) Optimal channel assignment and \(L(p,1)\)-labeling. J Global Optim 72:539–552
Zhu HY, Zhu JL, Liu Y, Wang SL, Huang DJ, Miao LY (2020) The list L(2,1) –labeing of planar graps with large girth, In: Zhang Z, Li W, Du DZ (eds) Algorithmic applications in management AAIM 2020: lecture notes in computer science, 12290, pp 501–512
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
Conflict of interest
The authors declare that they have no conflict of interest.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
This research was supported by National Science Foundation of China under Grant Nos.11901243, 11771403 and Zhejiang Provincial Natural Science Foundation of China under Grant Nos. LQ19A010005, LY18A010014)
Rights and permissions
About this article
Cite this article
Zhu, H., Zhu, J., Liu, Y. et al. Optimal frequency assignment and planar list L(2, 1)-labeling. J Comb Optim 44, 2748–2761 (2022). https://doi.org/10.1007/s10878-021-00791-5
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10878-021-00791-5