Abstract
A list assignment of G is a function L that assigns to each vertex \(v\in V(G)\) a list L(v) of available colors. Let r be a positive integer. For a given list assignment L of G, an (L, r)-coloring of G is a proper coloring \(\phi \) such that for any vertex v with degree d(v), \(\phi (v)\in L(v)\) and v is adjacent to at least \( min\{d(v),r\}\) different colors. The list r-hued chromatic number of G, \(\chi _{L,r}(G)\), is the least integer k such that for every list assignment L with \(|L(v)|=k\), \(v\in V(G)\), G has an (L, r)-coloring. We show that if \(r\ge 32\) and G is a planar graph without 4-cycles, then \(\chi _{L,r}(G)\le r+8\). This result implies that for a planar graph with maximum degree \(\varDelta \ge 26\) and without 4-cycles, Wagner’s conjecture in [Graphs with given diameter and coloring problem, Technical Report, University of Dortmund, Germany, 1977] holds.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Akbari S, Ghanbari M, Jahanbekam S (2009) On the list dynamic coloring of graphs. Discrete Appl Math 157:3005–3007
Bonamy M, Lévêque B, Pinlou A (2014) Graphs with maximum degree \(\varDelta \ge 17\) and maximum average degree less than 3 are list 2-distance \((\varDelta + 2)\)-colorable. Discrete Math 317:19–32
Bondy JA, Murry USR (2008) Graph theory. Springer, New York
Borodin OV, Broersma HJ, Glebov A, van den Heuvel J (2002) Stars and bunches in planar graphs. Part: General planar graphs and colorings, Technical Report, London School of Economics
Chen Y, Fan S-H, Lai H-J, Song H-M, Sun L (2012) On dynamic coloring for planar graphs and graphs of higher genus. Discrete Appl Math 160:1064–1071
Ding C, Fan S-H, Lai HJ (2008) Upper bound on conditional chromatic number of graphs. J Jinan Univ 29:7–14
Havet F, van den Heuvel J, McDiarmid C, Reed B (2007) List colouring squares of planar graphs. Electron Notes Discrete Math 29:515–519
Havet F (2009) Choosability of the square of planar subcubic graphs with large girth. Discrete Math 309:3553–3563
Ivanova AO (2011) List 2-distance \((\varDelta +1)\)-coloring of planar graphs with girth at least 7. J Appl Ind Math 5(2):22–36
Lai H-J, Montgomery B, Poon H (2003) Upper bounds of dynamic chromatic number. Ars Comb 68:193–201
Lai H-J, Lin J, Montgomery B, Tao Z, Fan S-H (2006) Conditional colorings of graphs. Discrete Math 306:1997–2004
Lin Y (2008) Upper bounds of conditional chromatics number, Master Thesis, Jinan University
Molloy M, Salavatipour MR (2005) A bound on the chromatic number of the square of a planar graph. J Comb Theory Ser B 94:189–213
Montgomery B (2001) Ph.D. Dissertation, West Virginia University
Song H-M, Fan S-H, Chen Y, Sun L, Lai H-J (2014) On \(r\)-hued coloring of \(K_4\)-minor free graphs. Discrete Math 315–316:47–52
Wegner G (1977) Graphs with given diameter and coloring problem, Technical Report, University of Dortmund
Acknowledgements
Research supported partially by NSFC (Nos. 61170302 and 11601105).
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Zhu, H., Chen, S., Miao, L. et al. On list r-hued coloring of planar graphs. J Comb Optim 34, 874–890 (2017). https://doi.org/10.1007/s10878-017-0118-0
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10878-017-0118-0