×

List precoloring extension in planar graphs. (English) Zbl 1223.05062

Summary: A celebrated result of Thomassen states that not only can every planar graph be colored properly with five colors, but no matter how arbitrary palettes of five colors are assigned to vertices, one can choose a color from the corresponding palette for each vertex so that the resulting coloring is proper. This result is referred to as 5-choosability of planar graphs. Albertson asked whether Thomassen’s theorem can be extended by precoloring some vertices which are at a large enough distance apart in a graph. Here, among others, we answer the question in the case when the graph does not contain short cycles separating precolored vertices and when there is a “wide” Steiner tree containing all the precolored vertices.

MSC:

05C15 Coloring of graphs and hypergraphs
05C10 Planar graphs; geometric and topological aspects of graph theory
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Albertson, M., You can’t paint yourself into a corner, J. Combin. Theory Ser. B, 73, 189-194 (1998) · Zbl 0910.05026
[2] Böhme, T.; Mohar, B.; Stiebitz, M., Dirac’s map-color theorem for choosability, J. Graph Theory, 32, 4, 327-339 (1999) · Zbl 0941.05025
[3] P. Erdős, A.L. Rubin, H. Taylor, Choosability in graphs, in: Proceedings of the West Coast Conference on Combinatorics, Graph Theory and Computing, Humboldt State Univ., Arcata, Calif., 1979, Congress. Numer., Utilitas Math., Winnipeg, Man., vol. XXVI, 1980, pp. 125-157.; P. Erdős, A.L. Rubin, H. Taylor, Choosability in graphs, in: Proceedings of the West Coast Conference on Combinatorics, Graph Theory and Computing, Humboldt State Univ., Arcata, Calif., 1979, Congress. Numer., Utilitas Math., Winnipeg, Man., vol. XXVI, 1980, pp. 125-157.
[4] Kostochka, A. V.; Stiebitz, M.; Wirth, B., The colour theorems of Brooks and Gallai extended, Discrete Math., 162, 1-3, 299-303 (1996) · Zbl 0871.05024
[5] Mirzakhani, M., A small non-4-choosable planar graph, Bull. Inst. Combin. Appl., 17, 15-18 (1996) · Zbl 0860.05029
[6] Thomassen, C., Color-critical graphs on a fixed surface, J. Combin. Theory Ser. B, 70, 1, 67-100 (1997) · Zbl 0883.05051
[7] Thomassen, C., Every planar graph is 5-choosable, J. Combin. Theory Ser. B, 62, 180-181 (1994) · Zbl 0805.05023
[8] Thomassen, C., Exponentially many 5-list-colorings of planar graphs, J. Combin. Theory Ser. B, 97, 4, 571-583 (2007) · Zbl 1123.05043
[9] Tuza, Zs.; Voigt, M., A note on planar 5-list-colouring: non-extendability at distance 4, Discrete Math., 251, 169-172 (2002) · Zbl 1002.05020
[10] Vizing, V. G., Coloring the vertices of a graph in prescribed colors, Metody Diskret. Anal. v Teorii Kodov i Schem, 29, 3-10 (1976), (in Russian) · Zbl 1249.90303
[11] Voigt, M., List colourings of planar graphs, Discrete Math., 120, 1-3, 215-219 (1993) · Zbl 0790.05030
[12] Voigt, M.; Wirth, B., On 3-colorable non-4-choosable planar graphs, J. Graph Theory, 24, 3, 233-235 (1997) · Zbl 0868.05025
[13] West, D. B., Introduction to Graph Theory (2001), Prentice Hall
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.