この用語はまだ監査を通っていません（未確認）。
グラフ彩色
ぐらふさいしょく ／ 彩色 1対1で対応vertex coloring
名詞 別の言い方 graph coloring
式と読み方
chi of G
定義
グラフの各頂点に色を割り当て、辺で結ばれた 2 頂点が必ず異なる色になるようにすること。必要な色の最小の個数を彩色数という。
An assignment of colors to the vertices of a graph so that any two vertices joined by an edge get different colors. The smallest number of colors needed is the chromatic number.
例文
話し言葉 In a vertex coloring, neighbors can't share a color, so a triangle already needs three colors. 彩色では隣り合う頂点に同じ色を使えないので、三角形だけでもう 3 色必要になる。
書き言葉・答案 Find a vertex coloring of the graph below that uses as few colors as possible, and state the chromatic number of the graph. 下のグラフを、できるだけ少ない色の数で彩色せよ。また、このグラフの彩色数を答えよ。
言い間違えやすいところ
- 見出しの vertex coloring は Levin の本の呼び方（10 件、2.5 Coloring 7・2.1 Problems and Definitions 3）。graph coloring は Levin で 5 件。用例コーパスでは話し言葉（MIT OCW）に出てくるが、書き言葉にはほとんど出てこない。
- 辺に色を付ける edge coloring（辺彩色）は別の問題。彩色数は chromatic number で、χ(G)（chi of G）と書く。
- 平面グラフはどれも 4 色以内で彩色できる（四色定理、four color theorem）。