TOPICS
Search

List Coloring

List coloring of a finite simple graph is a proper coloring in which the color of each graph vertex is chosen from a prescribed finite set of available colors, called its list. The lists may differ from one graph vertex to another (Dvorák and Postle 2018).

For a nonnegative integer k, a graph is k-choosable iff every assignment of lists with k colors in each list admits a list coloring. The least such k is its choice number, also called its list chromatic number (Gu and Xu 2026, p. 1).

See also

Choice Number, Correspondence Coloring, Graph Coloring, List Color Function, Proper Coloring, Vertex Coloring

Explore with Wolfram|Alpha

References

Dvorák, Z. and Postle, L. "Correspondence Coloring and Its Application to List-Coloring Planar Graphs Without Cycles of Lengths 4 to 8." J. Combin. Th. Ser. B 129, 38-54, 2018. https://doi.org/10.1016/j.jctb.2017.09.001.Gu, Y. and Xu, R. "Improved Upper Bounds on the List Chromatic Number of K_t-Minor-Free Graphs." 1 Oct 2026. https://arxiv.org/abs/2610.01946v1.

Cite this as:

Weisstein, Eric W. "List Coloring." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/ListColoring.html

Subject classifications