全体的な着色

数学における未解決問題

推測：$\displaystyle \chi ''(G)\leq \Delta (G)+2.}$

数学における未解決問題

グラフ理論において、全彩色とは、グラフの頂点と辺に対するグラフ彩色の一種です。特に条件を付けずに使用する場合、全彩色は常に、隣接する辺、隣接する頂点、辺と両端の頂点のいずれにも同じ色が割り当てられないという意味で適切であるとみなされます。グラフGの全彩色数χ ″( G )は、 Gの任意の全彩色に必要な最小の色数です。

グラフGの全グラフT = T ( G )は、(i) Tの頂点集合がGの頂点と辺に対応し、(ii) 2 つの頂点がTで隣接しているのは、対応する要素がGで隣接しているか、または隣接している場合に限る、という条件を満たすグラフです。このとき、 Gの全彩色は、T ( G )の(適切な) 頂点彩色になります。全彩色とは、グラフの頂点と辺を全独立集合に分割することです。

χ ″( G )に関するいくつかの不等式：

1. ${\displaystyle \chi ''(G)\geq \Delta (G)+1.}$
2. ${\displaystyle \chi ''(G)\leq \Delta (G)+10^{26}.}$ （モロイ、リード 1998）
3. ${\displaystyle \chi ''(G)\leq \Delta (G)+8\ln ^{8}(\Delta (G))}$Δ ( G )が十分に大きい場合。（Hind、Molloy、Reed 1998）
4. ${\displaystyle \chi ''(G)\leq \operatorname {ch} '(G)+2.}$

ここで、Δ( G )は最大次数、ch′( G )はエッジ選択可能性です。

総彩色とは、頂点彩色と辺彩色を単純に組み合わせたものであるため、自然に生じます。次のステップは、最大次数に関して、総彩色数のブルックス型またはヴィジング型の上限を探すことです。

最大次数上限の完全彩色版は、50年間数学者を悩ませてきた難問である。χ″(G)の自明な下限はΔ ( G ) +1である。長さのサイクルなどのグラフは${\displaystyle n\not \equiv 0{\bmod {3}}}$また、 K _n,nの形の完全二部グラフはΔ( G ) + 2色を必要としますが、それ以上の色を必要とするグラフは見つかっていません。このことから、すべてのグラフはΔ( G ) + 1 色またはΔ( G ) + 2色を必要とし、それ以上は必要としないという推測が導き出されます。

完全彩色予想（ベザード、ヴィジン）。$\displaystyle \chi ''(G)\leq \Delta (G)+2.}$

どうやら、「全彩色」という用語と全彩色予想の記述は、1964年から1968年の間にベザードとヴィジングによって何度も独立して提唱されたようです（ジェンセン＆トフトを参照）。この予想は、すべての二部グラフや、最大次数が6のグラフを除くほとんどの平面グラフなど、いくつかの重要なグラフクラスで成り立つことが知られています。平面グラフの場合については、ヴィジングの平面グラフ予想が真であれば完全です。また、リスト彩色予想が真であれば、$\displaystyle \chi ''(G)\leq \Delta (G)+3.}$

全彩色に関する結果が得られています。例えば、KilakosとReed（1993）は、グラフGの全グラフの分数彩色数は最大でΔ( G )+2であることを証明しました。

• Hind, Hugh; Molloy, Michael; Reed, Bruce (1998). "Δ + poly(log Δ) 色による全彩色". SIAM Journal on Computing . 28 (3): 816–821 . doi : 10.1137/S0097539795294578 .
• ジェンセン、トミー・R.、トフト、ビャルネ（1995）。グラフ彩色問題。ニューヨーク：ワイリー・インターサイエンス。ISBN 0-471-02865-7。
• Kilakos, Kyriakos; Reed, Bruce (1993). "全グラフの分数彩色". Combinatorica . 13 (4): 435–440 . doi : 10.1007/BF01303515 . S2CID 31163141 . 
• Molloy, Michael; Reed, Bruce (1998). "全彩色数の上限". Combinatorica . 18 (2): 241–280 . doi : 10.1007/PL00009820 . hdl : 1807/9465 . S2CID 9600550 .