Listfärgningen

Listfärgningen, known in English as list coloring, is a concept in graph theory that studies colorings where each vertex comes with its own allowed color set. Given a graph G = (V, E) and a list assignment L that assigns to every vertex v a set L(v) of permissible colors, an L-coloring is a vertex coloring in which each vertex v is colored with a color from L(v) and adjacent vertices receive different colors. If a graph G can be colored from every list assignment with |L(v)| ≥ k for all v, then G is k-choosable. The smallest k with this property is the choice number ch(G).

Key terms and ideas include the list analogue of ordinary coloring, the notion of choosability, and the comparison to the chromatic number χ(G). A graph is k-choosable precisely when, no matter how one assigns lists of size at least k to the vertices, a proper coloring from those lists exists. Thus χ(G) ≤ ch(G), with equality in many but not all cases.

History and notable results: Listfärgningen was introduced by Erdős, Rubin, and Taylor in 1989 as a natural generalization of graph coloring. A foundational result is Thomassen’s theorem (1994), proving that every planar graph is 5-choosable. It is also known that every bipartite graph is 2-choosable, and complete graphs have choice number equal to their order (ch(Kn) = n). Ohba’s conjecture, relating choice number and chromatic number for certain graphs, was eventually resolved affirmatively by Nöl and Reed.

Applications and related topics include scheduling, resource allocation, and frequency assignment, as well as further study of choosability, list-critical graphs, and precoloring extension problems.