List colourings of planar graphs

By M. Voigt. Discrete Mathematics, 2006

305 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Breaking the degeneracy barrier for coloring graphs with no K minor (2019, result): “is a choice of colors {c(v)}v∈V (G) such that c(v) ∈ L(v), and c(v) 6= c(u) for every uv ∈ E(G). Clearly every k-list colorable graph is k-colorable, but the converse implication does not hold. Voigt [Voi93] has shown that there exist planar graphs which are not 4-list colorable. Generalizing the re”
An extremal problem for H -linked graphs (2005, background): “The version of Brooks’ Theorem for list-chromatic number implies that if G is a graph on the Klein bottle, then also ‘(G) 6. For graphs on the sphere, the maximum chromatic number is 4, but the maximum list-chromatic number is 5 (upper bound by Thomassen [21], lower bound by Voigt [ 22 ]).”
Complexity of clique-coloring odd-hole-free graphs (2009, background): “Observe that this does not hold for the usual list colouring, since Voigt [15] proved that there exist planar graphs which are not 4-choosable.”
Defective and Clustered Graph Colouring (2018, background): “Voigt [213] and later Mirzakhani [175] constructed planar graphs that are not 4-choosable.”