Abstract
We consider a natural restriction of the List Colouring problem, k-Regular List Colouring, which corresponds to the List Colouring problem where every list has size exactly k. We give a complete classification of the complexity of k-Regular List Colouring restricted to planar graphs, planar bipartite graphs, planar triangle-free graphs and to planar graphs with no 4-cycles and no 5-cycles. We also give a complete classification of the complexity of this problem and a number of related colouring problems for graphs with bounded maximum degree.
First and last author supported by EPSRC (EP/K025090/1).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Alon, N., Tarsi, M.: Colorings and orientations of graphs. Combinatorica 12, 125–134 (1992)
Appel, K., Haken, W.: Every planar map is four colorable, Contemporary Mathematics 89, AMS Bookstore (1989)
Brooks, R.L.: On colouring the nodes of a network. Math. Proc. Camb. Philos. Soc. 37, 194–197 (1941)
Chen, M., Montassier, M., Raspaud, A.: Some structural properties of planar graphs and their applications to 3-choosability. Discrete Math. 312, 362–373 (2012)
Chlebík, M., Chlebíková, J.: Hard coloring problems in low degree planar bipartite graphs. Discrete Appl. Math. 154, 1960–1965 (2006)
Chudnovsky, M.: Coloring graphs with forbidden induced subgraphs. Proc. ICM IV, 291–302 (2014)
Dvořák, Z., Lidický, B., Škrekovski, R.: Planar graphs without 3-, 7-, and 8-cycles are 3-choosable. Discrete Math. 309, 5899–5904 (2009)
Emden-Weinert, T., Hougardy, S., Kreuter, B.: Uniquely colourable graphs and the hardness of colouring graphs of large girth. Comb. Probab. Comput. 7, 375–386 (1998)
Erdős, P., Rubin, A.L., Taylor, H.: Choosability in graphs. In: Proceedings of the West Coast Conference on Combinatorics, Graph Theory and Computing (Humboldt State Univ., Arcata, Calif., 1979), Congress. Numer., XXVI, pp. 125–157. Winnipeg, Man., Utilitas Math. (1980)
Garey, M.R., Johnson, D.S., Stockmeyer, L.J.: Some simplified \({\sf NP}\)-complete graph problems. In: Proceedings of STOC, pp. 47–63 (1974)
Golovach, P.A., Heggernes, P., van ’t Hof, P., Paulusma, D.: Choosability on \(H\)-free graphs. Inform. Process. Lett. 113, 107–110 (2013)
Golovach, P.A., Johnson, M., Paulusma, D., Song, J.: A survey on the computational complexity of colouring graphs with forbidden subgraphs, Manuscript, arXiv:1407.1482v4 (2014)
Gutner, S.: The complexity of planar graph choosability. Discrete Math. 159, 119–130 (1996)
Kratochvíl, J.: Precoloring extension with fixed color bound. Acta Mathematica Universitatis Comenianae 62, 139–153 (1993)
Kratochvíl, J., Tuza, Z.: Algorithmic complexity of list colourings. Discrete Appl. Math. 50, 297–302 (1994)
Lam, P.C.B., Xu, B., Liu, J.: The 4-choosability of plane graphs without 4-cycles. J. Comb. Theory Ser. B 76, 117–126 (1999)
Molloy, M., Reed, B.: Colouring graphs when the number of colours is almost the maximum degree. J. Comb. Theory Ser. B 109, 134–195 (2014)
Montassier, M.: A note on the not 3-choosability of some families of planar graphs. Inform. Process. Lett. 99, 68–71 (2006)
Montassier, M., Raspaud, A., Wang, W.: Bordeaux 3-color conjecture and 3-choosability. Discrete Math. 306, 573–579 (2006)
Thomassen, C.: Every planar graph is \(5\)-choosable. J. Comb. Theory Ser. B 62, 180–181 (1994)
Thomassen, C.: 3-List-coloring planar graphs of girth 5. J. Comb. Theory Ser. B 64, 101–107 (1995)
Vizing, V.G.: Coloring the vertices of a graph in prescribed colors. In: Diskret. Analiz., no. 29, Metody Diskret. Anal. v. Teorii Kodov i Shem, vol. 101, pp. 3–10 (1976)
Vizing, V.G.: Vertex colorings with given colors. Diskret. Analiz. 29, 3–10 (1976)
Voigt, M.: List colourings of planar graphs. Discrete Math. 120, 215–219 (1993)
Voigt, M.: A not 3-choosable planar graph without 3-cycles. Discrete Math. 146, 325–328 (1995)
Voigt, M.: A non-3-choosable planar graph without cycles of length 4 and 5. Discrete Math. 307, 1013–1015 (2007)
Wang, Y., Lu, H., Chen, M.: Planar graphs without cycles of length 4, 5, 8, or 9 are 3-choosable. Discrete Math. 310, 147–158 (2010)
Wang, Y., Lu, H., Chen, M.: Planar graphs without cycles of length 4, 7, 8, or 9 are 3-choosable. Discrete Appl. Math. 159, 232–239 (2011)
Wang, D.-Q., Wen, Y.-P., Wang, K.-L.: A smaller planar graph without 4-, 5-cycles and intersecting triangles that is not 3-choosable. Inform. Process. Lett. 108, 87–89 (2008)
Acknowledgements
We thank Steven Kelk for helpful comments on an earlier version of this paper.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer International Publishing Switzerland
About this paper
Cite this paper
Dabrowski, K.K., Dross, F., Johnson, M., Paulusma, D. (2016). Filling the Complexity Gaps for Colouring Planar and Bounded Degree Graphs. In: Lipták, Z., Smyth, W. (eds) Combinatorial Algorithms. IWOCA 2015. Lecture Notes in Computer Science(), vol 9538. Springer, Cham. https://doi.org/10.1007/978-3-319-29516-9_9
Download citation
DOI: https://doi.org/10.1007/978-3-319-29516-9_9
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-29515-2
Online ISBN: 978-3-319-29516-9
eBook Packages: Computer ScienceComputer Science (R0)