辺彩色・辺彩色数

写像 $c:E(G)\to S$ で、端点を共有するどの 2 辺にも異なる色を与えるものを辺彩色という。$|S|=k$ の辺彩色をもつような最小の $k$ を辺彩色数 $\chi'(G)$ という。辺彩色 $c$ と頂点 $v$ について、$v$ に接続するどの辺の色でもない色は、$v$ で欠けているという。