Status
On this page
Status
Topics
Status
On this page
Status
Topics
The list chromatic number is defined to be the minimal such that for any assignment of a list of colours to each vertex of (perhaps different lists for different vertices) a colouring of each vertex by a colour on its list can be chosen such that adjacent vertices receive distinct colours.
Does every planar graph have ? Is this best possible?
Source: erdosproblems.com/631
An accepted solution exists. The statement is true.
Proved. The site answers both questions yes: it credits Thomassen [Th94] with the upper bound for all planar and Voigt [Vo93] with a planar graph that is not -choosable, so the bound is sharp, and credits Gutner [Gu96] with a simpler construction, a planar graph of vertices against Voigt's . Each result is an accepted partial claim, Thomassen for the first question and Voigt and Gutner for the second, as is Mirzakhani's -vertex witness, which the site does not credit but the discussion thread links. The problem page lists the two questions as its parts, the upper bound and its sharpness, and the accepted partial claims settle both, so the standing derived from the claim pages is solved with the claim proved. See also Problem 630.