リスト彩色・リスト彩色数

各頂点 $v$ に色の有限集合 $L(v)$（リスト）が与えられているとき、彩色 $c$ ですべての $v$ について $c(v)\in L(v)$ となるものを $L$-彩色という。どの頂点のリストも $k$ 色以上であるようなどんな $L$ に対しても $L$-彩色があるとき、$G$ は $k$-リスト彩色可能であるという。そのような最小の $k$ をリスト彩色数 $\operatorname{ch}(G)$ という。