Abstract
The problem of list coloring of graphs appears in practical problems concerning channel or frequency assignment. In this paper, we study the minimum number of choosability of planar graphs. A graph G is edge-k-choosable if whenever every edge x is assigned with a list of at least k colors, L(x)), there exists an edge coloring \(\phi \) such that \(\phi (x) \in L(x)\). Similarly, A graph G is toal-k-choosable if when every element (edge or vertex) x is assigned with a list of at least k colors, L(x), there exists an total coloring \(\phi \) such that \(\phi (x) \in L(x)\). We proved \(\chi '_{l}(G)=\Delta \) and \(\chi ''_{l}(G)=\Delta +1\) for a planar graph G with maximum degree \(\Delta \ge 8\) and without chordal 6-cycles, where the list edge chromatic number \(\chi '_{l}(G)\) of G is the smallest integer k such that G is edge-k-choosable and the list total chromatic number \(\chi ''_{l}(G)\) of G is the smallest integer k such that G is total-k-choosable.
This is a preview of subscription content, log in via an institution to check access.
References
Borodin OV, Kostochka AV, Woodall DR (1997) List edge and list total colourings of multigraphs. J Comb Theory Ser B 71:184–204
Du HW, Jia XH, Li DY, Wu WL (2004) Coloring of double disk graphs. J Glob Optim 28:115–119
Hägkvist R, Chetwynd A (1992) Some upper bounds on the total and list chromatic numbers of multigraphs. J Graph Theory 16:503–516
Hou JF, Liu GZ, Cai JS (2006) List edge and list total colorings of planar graphs without 4-cycles. Theor Comput Sci 369:250–255
Jensen T, Toft B (1995) Graph coloring problems. Wiley, New York
Li R, Xu BG (2011) Edge choosability and total choosability of planar graphs with no 3-cycles adjacent 4-cycles. Discrete Math 311:2158–2163
Liu B, Hou JF, Wu JL, Liu GZ (2009) Total colorings and list total colorings of planar graphs without intersecting 4-cycles. Discrete Math 309:6035–6043
Wang HJ, Wu LD, Zhang X, Wu WL, Liu B (2016) A note on the minimum number of choosability of planar graphs. J Comb Optim 31:1013–1022
Wang HJ, Wu LD, Wu WL, Pardalos PM, Wu JL (2014) Minimum total coloring of planar graph. J Glob Optim 60:777–791
Wang W, Liu X (2005) List coloring based channel allocation for open-spectrum wireless networks. In: 2005 IEEE 62nd vehicular technology conference (VTC 2005-Fall) 1, pp 690–694. https://doi.org/10.1109/VETECF.2005.1558001
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Wang, H., Liu, B., Gai, L. et al. Minimum choosability of planar graphs. J Comb Optim 36, 13–22 (2018). https://doi.org/10.1007/s10878-018-0280-z
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10878-018-0280-z