4choosable

4choosable is a term in graph theory describing a specific colorability property related to lists of available colors for each vertex. A graph G is 4-choosable if, for every assignment L that maps every vertex v to a list L(v) of four colors, there exists a proper vertex coloring c of G such that c(v) is an element of L(v) for every vertex v. The general notion is called list coloring, and the smallest integer k for which a graph is k-choosable is called its list-chromatic number, denoted ch(G). Thus, G being 4-choosable means ch(G) ≤ 4.

4-choosability sits between ordinary colorability and stronger list-coloring statements. If a graph is 4-choosable, then it is certainly 4-colorable, since a universal list of four colors yields a valid coloring. However, the converse is not true in general: some graphs are 4-colorable but not 4-choosable. The property also interacts with graph classes in meaningful ways.

Key results include planarity-related theorems. Thomassen proved that every planar graph is 5-choosable, implying planar graphs are 5-colorable in the list-coloring sense. It is not true that all planar graphs are 4-choosable; Voigt constructed planar graphs that are not 4-choosable, showing the property does not extend from 5 to 4 in the planar setting.

Beyond planar graphs, there exist non-4-choosable graphs in general, and determining 4-choosability for a given graph is computationally challenging in many cases.