listchromatic

Listchromatic, in the context of graph theory, refers to the study of list colorings and the associated invariant known as the list chromatic number. Given a graph G, a list assignment L assigns to each vertex v a set L(v) of allowed colors. An L-coloring is a proper coloring of G in which every vertex v is colored with a color from its list L(v). A graph is L-colorable if such a coloring exists. The list chromatic number χ_l(G) is the smallest integer k such that for every list assignment L with |L(v)| ≥ k for all vertices v, G has an L-coloring. Equivalently, χ_l(G) is the minimum k for which every possible choice of color lists with at least k colors per vertex permits a proper coloring.

Relation to ordinary chromatic number: χ_l(G) is always at least χ(G), the ordinary chromatic number. In general the list chromatic number can be strictly larger than the ordinary chromatic number. For example, there exist planar graphs that are not 4-choosable, which shows χ_l(G) > 4 for some planar graphs, while Thomassen proved that every planar graph is 5-choosable, giving χ_l(G) ≤ 5 for planar graphs.

History and generalizations: The concept was introduced by Erdős, Rubin, and Taylor in 1989 under the notion of choosability. It has since become a central topic in graph coloring, with extensions such as DP-coloring (correspondence coloring), which generalizes list coloring further.

Computation: Deciding whether a given graph G with a specific list assignment L is L-colorable is NP-complete in general. For fixed k ≥ 3, determining whether χ_l(G) ≤ k is also NP-complete in many graph classes.