首先介绍列表染色的定义：

列表染色(List coloring): 对于图$G$, 给其每个点一个颜色列表$L$, 则称正常染色$\phi$为列表染色$L$-染色，如果$v\in V(G),\ \phi(v)\in L(v)$.

$k$-可选图: 对于图$G$, 任给其每个点一个$k$列表$L_k$, 都存在$L_k$-列表染色，则称图$G$是$k$-可选图。记$\chi_l(G)=min\{k\}$为列表染色数。

显然，正常染色数$\chi(G)\leq\chi_l(G)$, 因为若给每个点均取一样的染色列表，此时列表染色就退化成正常染色。但$chi_l(G)-\chi(G)$可能会取到非常大的值。

命题 1.1 令$k$是一个正整数，$n=\tbinom{2k-1}{k}$, 考虑完全二部图$K_{n,n}$, 断言其$\chi_l(K_{n,n})>k$.

证： 反证，假设$\chi_l(K_{n,n})\leq k$, 将$K_{n,n}$的点集划分为$A,B$两部，则给$A$中的每个点都赋予各不相同的$k$元列表$L$, 假设$G$有一个$L$-染色$\phi$，则断言$\phi$在$A$中至少使用了$k$种颜色。否则， 当选了第$j$种颜色时，剩余的种类数为$tbinom{2k-2}{k-1}$

k=3，10个点，颜色种类一共是1，2，3，4，5： {1，2，3}{4,5,1}{1,3,4}{1,3,5}{1,2,4}{1,2,5}{2,3,4}{2,3,5}{2,4,5}{3,4,5} 1 1 1 1 1 1 2 2 2 3 $k$-退化：遍历图$G$的所有子图$H$, 若$k=max_{H\subset G}\{\delta(H)\}$, 则称图$G$是$k$-退化的。