彩色・彩色数・クリーク数

集合 $S$ への写像 $c:V(G)\to S$ で、隣接するどの 2 頂点 $u,v$ についても $c(u)\ne c(v)$ となるものを $G$ の（頂点）彩色といい、$S$ の元を色という。$|S|=k$ のとき $k$-彩色という（定義 6.1［平面グラフ］ と同じ）。色 $s$ の頂点の全体 $c^{-1}(s)$ を色クラスという。$G$ が $k$-彩色をもつような最小の $k$ を彩色数 $\chi(G)$ という。

どの 2 頂点も隣接する頂点集合をクリークといい、クリークの頂点数の最大値をクリーク数 $\omega(G)$ という。