グラフ彩色 - Wikipedia

3色に頂点彩色（最適彩色）されたグラフ。ピーターセングラフの彩色数は3である。 グラフ彩色（グラフさいしょく、英: Graph coloring）とは、グラフの何らかの要素に、ある制約条件を満たすように色を割り当てることである。最も単純なものは、隣接する頂点同士が同じ色にならないように全頂点に彩色する問題である。これを頂点彩色（ちょうてんさいしょく）という。同様に辺彩色（へんさいしょく）は、隣接する辺同士が同じ色にならないように全辺を彩色する問題、面彩色（めんさいしょく）は、平面グラフの辺で囲まれた各領域（面）を隣接する面同士が同じ色にならないように彩色する問題である。 概要[編集] 頂点彩色が出発点であり、他の彩色問題は頂点彩色に変換可能である。例えば、辺彩色問題は、そのグラフをライングラフに変換したときの頂点彩色と同じであり、面彩色は平面グラフの双対グラフの頂点彩色と同じである。しかし

[takehikom]

1976年『四色定理の証明では初めて大規模にコンピュータを利用したことも注目に値する』『その証明の考え方はヘイウッドやケンプの考え方に沿ったもので、途中の数十年間の様々な努力は無視されている』