完全グラフと全彩色予想④

４，全彩色

　　グラフGの全彩色とは、Gの隣接するどの2元、または接続するどの2元も異なる色を持つようなGの元(頂点と辺)に色を付けることである。k個の色を用いる全彩色をk-全彩色という。グラフGに対して、k-全彩色が存在するときGはk-全彩色可能であるという。グラフGがk-全彩色可能であるようなkの最小値をGの全染色数といい、χ2(G)で表す。

　　グラフGの頂点彩色について、k-頂点彩色可能であるようなkの最小値をGの頂点染色数といい、χ(G)で表す。

　　定理４・１

　　　χ2(Kp)=p(pが奇数のとき)、p+1(pが偶数のとき)

　　　(証明)

　　　　完全グラフKp+1の線グラフをL(Kp+1)で表す。このとき、命題２・１より

　　　　　T(Kp)=L(Kp+1)

　　　　であるから、

　　　　　χ2(G)=χ( T(G) )

　　　　より、

　　　　　χ2(Kp)=χ( T(Kp) )=χ( L(Kp+1) )

　　　　となる。一般に任意の単純グラフGに対して、χ1(G)=χ( L(G) )が成立するから、

　　　　　χ1(Kp+1)=χ( L(Kp+1) )

　　　　である。定理３・１より、

　　　　　χ1(Kp+1)=p(pが奇数)、p+1(pが偶数)

　　　　となるから、

　　　　　χ2(Kp)=p(pが奇数)、p+1(pが偶数)

　　　　が得られる。(証明終わり)

　　命題４・２

　　　完全グラフKpがk-全彩色可能ならば、それから辺をi本(0≦i≦p(p-1)/2)取り除いた単純グラフGiはk-全彩色可能である。

　　　(証明)

　　　　(0)Kpから辺を0本取り除いたグラフG0は、Kpであり、k-全彩色可能である。

　　　　　このとき、2頂点の色と辺の色の辺の組み合わせ数はkC3=k!/( (k-3)!3! )個ある。組み合わせをc1、c2、、cmax(max=k!/( (k-3)!3! ) )とすると、Kpのときそれぞれの数はc(j、m)となる。

　　　　(1)Kpから辺を1本取り除いた単純グラフG1は、2頂点の色と辺の色の組み合わせの辺の色cjのそれぞれの数は0以上c(j、m)以下となるので、k-全彩色可能である。

　　　　(2)Kpから辺をi(i≠p(p-1)/2)本のとき、命題が成り立つとする。

　　　　　Kpから辺をi+1本取り除いた単純グラフGi+1は、2頂点の色と辺の色の組み合わせcjのそれぞれの数が0以上c(j、m)以下となるので、k-全彩色可能である。

　　　　(3)Kpから辺をp(p-1)/2本取り除いたグラフGp(p-1)/2は2頂点の色と辺の色の組み合わせcjがすべて0なので、k-全彩色可能である。

　　　　よって、命題は成り立つ。(証明終わり)

　　全彩色予想

　　　任意の単純グラフGに対して、最大次数をΔGとする。

　　　　χ2(G)≦ΔG+2

　　　である。

　　　(証明)

　　　　定理４・１と完全グラフKpの最大次数ΔKpがp-1より、

　　　　　χ2(Kp)=ΔKp+1(pが奇数)、ΔKp+2(pが偶数)

　　　　命題４・２より、

　　　　　χ2(Gi)≦ΔGi+1(位数が奇数)、ΔGi+2(位数が偶数)

　　　　よって、任意の単純グラフGはχ2(G)≦ΔG+2である。(証明終わり)