トータルカラーリング

グラフ理論において、全彩色はグラフの頂点と辺のグラフ彩色の一種である。何の条件も付けずに使用される場合、全彩色は常に、隣接する辺、隣接する頂点、および辺といずれかの端頂点に同じ色が割り当てられないという意味で適切であると想定される。グラフ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 )はエッジ選択可能性である。

総彩色は、単純に頂点彩色と辺彩色の混合なので、自然に生じます。次のステップは、最大次数に関して、総彩色の数の Brooks型またはVizing型の上限を探すことです。

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

全彩色予想( Behzad、Vizing)。${\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 Δ) colors によるトータルカラーリング」SIAM Journal on Computing . 28 (3): 816–821. doi :10.1137/S0097539795294578.
• Jensen, Tommy R.; Toft, Bjarne (1995).グラフ着色問題. ニューヨーク: Wiley-Interscience. ISBN 0-471-02865-7 . 
• Kilakos, Kyriakos; Reed, Bruce (1993). 「全グラフの部分的着色」. Combinatorica . 13 (4): 435–440. doi :10.1007/BF01303515. S2CID  31163141.
• モロイ、マイケル;リード、ブルース(1998) 。「総彩色数の上限」。コンビナトリカ。18 (2): 241–280。doi :10.1007/PL00009820。hdl : 1807/ 9465。S2CID  9600550 。