Definition
List coloring is a variant of graph coloring in which each vertex of a graph is assigned a list (or set) of permissible colors, and a proper coloring must select for each vertex a color from its own list such that adjacent vertices receive different colors.
Overview
In classical vertex coloring, a single palette of colors is available for all vertices, and the goal is to minimize the number of colors while ensuring adjacent vertices are differently colored. List coloring generalizes this problem by allowing the set of admissible colors to vary from vertex to vertex. A graph is said to be k‑choosable if, for every assignment of lists of size k to its vertices, there exists a proper coloring respecting those lists. The smallest such k is the list chromatic number (or choice number) of the graph. List coloring was introduced independently by Vizing (1976) and by Erdős, Rubin, and Taylor (1979) and has become a central topic in combinatorial graph theory, with connections to algorithmic complexity, extremal graph theory, and applications such as frequency assignment in wireless networks.
Etymology/Origin
The term combines “list,” referring to the explicit enumeration of allowable colors for each vertex, with “coloring,” a standard term in graph theory for assigning colors under adjacency constraints. The concept originated in the late 1970s as researchers explored extensions of the classic coloring problem to more constrained settings.
Characteristics
- List Assignment: For a graph $G = (V, E)$, a list assignment $L$ assigns to each vertex $v \in V$ a finite set $L(v)$ of colors.
- Proper List Coloring: A function $c : V \to \bigcup_{v\in V}L(v)$ is a proper list coloring if $c(v) \in L(v)$ for all $v$ and $c(u) eq c(v)$ for every edge $(u,v) \in E$.
- Choice Number: The choice number $\operatorname{ch}(G)$ is the minimum integer $k$ such that $G$ is $k$-choosable; i.e., for every list assignment with $|L(v)| \ge k$ for all $v$, a proper list coloring exists.
- Relations to Classical Chromatic Number: For any graph $G$, $\chi(G) \le \operatorname{ch}(G)$, where $\chi(G)$ is the ordinary chromatic number. Equality holds for many families (e.g., bipartite graphs, complete graphs), but there are graphs where the choice number exceeds the chromatic number (e.g., certain bipartite graphs constructed by Alon).
- Algorithmic Aspects: Determining whether a given list assignment admits a proper coloring is NP‑complete in general. However, polynomial‑time algorithms exist for special graph classes (e.g., trees, interval graphs) and for bounded list sizes.
- Variants: Extensions include edge list coloring (lists on edges), total list coloring (lists on both vertices and edges), and online list coloring (lists revealed sequentially).
Related Topics
- Graph coloring
- Chromatic number
- Choice number (list chromatic number)
- Edge coloring and Vizing’s theorem
- Perfect graphs
- Brooks’ theorem (and its list‑coloring analogues)
- Alon’s combinatorial nullstellensatz (used in list‑coloring proofs)
- Applications in frequency assignment, scheduling, and register allocation in compilers.