List colourings of planar graphs.

*(English)*Zbl 0790.05030In 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.

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.

Reviewer: D.S.Archdeacon (Burlington)

##### MSC:

05C15 | Coloring of graphs and hypergraphs |

05C10 | Planar graphs; geometric and topological aspects of graph theory |

PDF
BibTeX
XML
Cite

\textit{M. Voigt}, Discrete Math. 120, No. 1--3, 215--219 (1993; Zbl 0790.05030)

Full Text:
DOI

##### References:

[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, (), 5.-7.9, Congressus Numeratium XXVI. |

[4] | Lovász, L., Combinatorial problems and exercises, (1979), Akadémiai Kiadó Budapest · Zbl 0439.05001 |

[5] | N.V.R. Mahadev, F.S. Roberts and P. Santhanakrishnan, 3-choosable complete bipartite graphs, DIMACS, Technical Report 91-62. |

[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, () · 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.