グラフ彩色

グラフ彩色とは、隣接する要素が異なるようにグラフ要素にラベル（色）を割り当てることであり、必要とされる最小の色の数を研究する分野です。

Definition

グラフの適切な彩色とは、隣接するどの2つの頂点も同じ色を共有しないように、その頂点に色を割り当てることです。彩色数とは、そのような割り当てが存在する最小の色の数です。

Scope

このトピックでは、適切な頂点彩色と彩色数、辺彩色と彩色指数、彩色数を数える彩色多項式、およびブルックスの定理、ヴィージングの定理、平面グラフの四色定理を含む画期的な結果について扱います。また、彩色を独立性、クリーク、およびグラフパラメータのより広範な理論に結びつけます。

Core questions

• 与えられたグラフを適切に彩色するために必要な最小の色の数はいくつですか？
• 与えられたパレットで、グラフはいくつの適切な彩色を許容しますか？
• どのグラフが少ない色で彩色でき、どのような障害が多い色を強制しますか？
• 辺彩色とリスト彩色は基本的な概念をどのように拡張しますか？

Key concepts

• 適切な頂点彩色
• 彩色数
• 彩色多項式
• 辺彩色と彩色指数
• ブルックスの定理
• 四色定理

Key theories

四色定理

すべての平面グラフは高々4色で適切に彩色できるというもので、1世紀以上にわたって未解決であったこの命題は、1976年にアペルとハーケンによって広範なコンピュータ支援ケース分析を用いて初めて証明されました。

ヴィージングの定理

任意の単純グラフの辺は、最大次数または最大次数に1を加えた数のいずれかの色で適切に彩色でき、すべてのグラフを2つの狭いクラスに分類します。

Clinical relevance

彩色モデルは、競合のないリソース割り当てをモデル化します。衝突のないスケジューリング、コンパイラにおけるレジスタ割り当て、無線ネットワークにおける周波数割り当て、数独のような制約問題はすべてグラフ彩色に帰着されます。

History

1852年に提起された四色予想は、彩色理論の多くを推進しました。1976年のアペルとハーケンによるコンピュータ支援証明は、コンピュータ支援数学における初期の画期的な出来事であり、証明の性質に関する議論を巻き起こしました。

Debates

コンピュータ支援証明の現状

四色定理が機械で検証されたケースに依存していることは、人間が手作業で検証するには長すぎる証明が、真の数学的証明として数えられるべきかという問題を提起しました。

Key figures

• Kenneth Appel
• Wolfgang Haken
• Vadim Vizing

Seminal works

• diestel2017

Frequently asked questions

グラフの彩色数とは何ですか？

隣接する頂点が常に異なる色を受け取るために必要な最小の色の数です。例えば、奇数サイクルは彩色数3を持ちます。

四色定理はすべての地図に適用されますか？

領域が連結している平面または球面上に描かれた地図に適用されます。トーラスのような表面上の地図は、より多くの色を必要とする場合があります。