List colourings of planar graphs. (English) Zbl 0790.05030

In an ordinary vertex colouring there is a set of \(k\) colours available, and a vertex colouring picks one of these colours for each vertex so that adjacent vertices receive distinct colours. In a list colouring there is a pre-assigned list of colours at each vertex, and in a colouring a vertex must receive a colour from its list. A graph is \(k\)-choosable if there is a proper list colouring for any assignment of lists with at least \(k\) colours available at each vertex. The choice number of a graph is the smallest \(k\) so that it is \(k\)-choosable.
In general, it is possible that a graph’s choice number exceeds its chromatic number, in other words, the more general problem may be more difficult. However, the hope is that for special classes of graphs the choice number should be close to the chromatic number. Along these lines, two conjectures of Erdős, Rubin, and Taylor state that (1) there exists a planar graph which is not 4-choosable, and (2) any planar graph is 5- choosable. It is known that there are planar graphs which are not 3- choosable, and that every planar graph is 6-choosable.
The author presents a planar graph on 238 vertices which is not 4- choosable, therefore settling Conjecture (1) above. The second conjecture remains open.


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


[1] Albertson, M. O.; Berman, D. M., Cliques, colorings and locally perfect graphs, Congr. Numer., 39, 69-73 (1983) · Zbl 0576.05024
[2] Alon, N.; Tarsi, M., Colorings and orientations of graphs, Combinatorica, 12, 125-134 (1992) · Zbl 0756.05049
[3] Erdős, P.; Rubin, A. L.; Taylor, H., Choosability in Graphs, (Proceedings of the West Coast Conference on Combinatorics. Proceedings of the West Coast Conference on Combinatorics, Graph Theory and Computing (1979), Arcata: Arcata California), 5.-7.9, Congressus Numeratium XXVI.
[4] Lovász, L., Combinatorial Problems and Exercises (1979), Akadémiai Kiadó: Akadémiai Kiadó Budapest · Zbl 0439.05001
[6] Roberts, F. S., From garbage to rainbows: generalizations of graph coloring and their applications, RUTCOR Research Report, 36-88 (1988)
[7] Tesman, B., T-colorings, list T-colorings, and set T-colorings of graphs, (Ph.D. Thesis (1989), Department of Mathematics, Rutgers University: Department of Mathematics, Rutgers University New Brunswick, New Jersey) · Zbl 0788.05047
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.