正確な色付け

7色と14頂点による正確な色付けの例

グラフ理論において、完全彩色とは、すべての色のペアが隣接する頂点のペアのちょうど1つに現れるような（適切な）頂点彩色である。つまり、グラフの頂点を互いに素な独立集合に分割し、分割された異なる独立集合の各ペアに対して、各集合に端点を持つ辺がちょうど1つ存在するようなものである。^{[1] [2]}

完全グラフ、分離、オイラーツアー

完全グラフ K ₆の正確な着色

n頂点を持つすべての完全グラフ K _{n は}、各頂点に異なる色を与えることで得られるn色による正確な彩色を持つ。n色による正確な彩色を持つすべてのグラフは、完全グラフの分離として得られる。分離とは、完全グラフから各頂点を独立集合に分割し、その頂点に接する各辺を対応する独立集合の要素のちょうど1つに再接続することで得られるグラフである。^{[1] [2]}

kが奇数の場合、辺を持つパスまたはサイクルは完全彩色を持つ。これは、完全グラフK _kの完全彩色を形成し、この完全グラフのオイラー巡回を求めることで得られる。例えば、3つの辺を持つパスは完全3彩色を持つ。^[2]${\displaystyle {\tbinom {k}{2}}}$

関連する着色の種類

完全彩色は、調和彩色（各色のペアが最大で 1 回出現する彩色）や完全彩色（各色のペアが少なくとも 1 回出現する彩色）と密接に関連しています。明らかに、完全彩色は調和的かつ完全な彩色です。n頂点m辺のグラフGが調和k彩色を持つ場合と、孤立した辺を追加してGから作成したグラフが完全彩色を持つ場合とで同値です。同じパラメータを持つグラフGが完全k彩色を持つ場合と、GのサブグラフHで、 G  −  Hの各辺が異なる彩色の端点を持つような完全k彩色を持つものが存在する場合とで同値です。G − H の 辺に対する条件の必要性は、4 頂点サイクルの例で示されます。このサイクルには、完全 3 彩色（3 辺パス）を持つサブグラフがありますが、それ自体は完全 3 彩色を持ちません。^[2]${\displaystyle m\leq {\tbinom {k}{2}}}$ ${\displaystyle {\tbinom {k}{2}}-m}$ ${\displaystyle m\geq {\tbinom {k}{2}}}$

計算の複雑さ

与えられたグラフが正確な色付けを持つかどうかを判断することは、たとえグラフが木であってもNP完全である。^{[1] [3]しかし、この問題は、制限された}次数の木に対しては多項式時間で解ける可能性がある。^{[1] [4]}

参考文献

1. Edwards, Keith (2005)、「完全グラフの分離」、Combinatorics, Probability and Computing、14 (3): 275– 310、doi :10.1017/S0963548304006558、MR  2138114、S2CID  31563931。
2. Edwards, Keith (2010)、「断片化可能なグラフの無彩色数」、Journal of Graph Theory、65 (2): 94– 114、doi : 10.1002/jgt.20468、MR  2724490。
3. エドワーズ、キース; マクダーミッド、コリン (1995)、「木の調和的着色の複雑さ」、離散応用数学、57 ( 2–3 ): 133– 144、doi : 10.1016/0166-218X(94)00100-R、MR  1327772。
4. エドワーズ、キース（1996）、「境界付き次数木の調和的彩色数」、組合せ論、確率、計算、5（1）：15–28、doi：10.1017/S0963548300001802、MR  1395690、S2CID  860190。