列表着色

列表着色在普通顶点着色的基础上，给每个顶点指定一份允许使用的颜色列表。目标是从各自的列表中选择颜色，使相邻顶点颜色不同。不同顶点的列表可以不同。

定义与例子

设有限图 $G$ 的每个顶点 $v$ 有一个颜色集合 $L(v)$。若能选择 $c(v)\in L(v)$，并对每条边 $uv$ 满足 $c(u)\ne c(v)$，则称 $G$ 可以按列表 $L$ 着色。

考虑路径 $1-2-3$，指定 $$\begin{array}{cc}L(1)& =\{\text{蓝},\text{红}\},\\ L(2)& =\{\text{红},\text{绿}\},\\ L(3)& =\{\text{蓝},\text{绿}\}.\end{array}$$ 图中用 $B,R,G$ 分别表示蓝、红、绿。选 $c(1)=\text{蓝},c(2)=\text{红},c(3)=\text{绿}$，每个选择都在对应列表里，且两条边的端点颜色不同。这只说明这个特定列表可以着色，还不能说明任意同样大小的列表都可以。

例子中分别选 B、R、G；每个点只能从自己的两个候选颜色中选取。

列表色数

如果对每一种满足 $|L(v)|\ge k$ 的列表分配都存在合法着色，就称 $G$ 是 $k$ 可选择的。满足此条件的最小 $k$ 称为列表色数或可选择数，记为 $\mathrm{ch}(G)$。这一定义对所有列表分配作要求，不能仅凭找到一个成功的列表来断言图是 $k$ 可选择的。

把每个顶点的列表都取为同一个 $k$ 色集合，得到普通的 $k$ 着色问题。因此 $$\mathrm{ch}(G)\ge \chi (G).$$ 列表色数可能严格大于普通色数，因为不同列表额外限制了每个顶点能够选择的颜色。

森林的列表色数

每棵树选一个根，先给根任取列表中的颜色，再依照从根向外的顺序给其余顶点着色。给某顶点着色时，至多已有它的父顶点被着色；如果列表至少含两种颜色，就至少有一种与父顶点不同。对森林的各个连通分量分别执行，证明每个森林都是 2 可选择的。

如果森林至少有一条边，让该边两个端点的列表都只含同一种颜色，就不可能合法着色，所以它不是 1 可选择的。因此有边的森林列表色数恰好为 2；非空且没有边的图列表色数为 1。这里的证明利用树的结构，不表示所有二部图都能对任意两元素列表着色。