リスト彩色とリスト彩色予想②

２，リスト彩色予想

　リスト彩色予想

　　任意の単純グラフGは、ch1(G)=χ1(G)である。

　(証明)

　　1つ反例を示すことで、予想を否定する。

　　完全グラフKpの位数が奇数の場合を考える。Kpのサイズqはp(p-1)/2である。

　　完全グラフKpに対してχ1(Kp)=p(pが奇数)、p-1(pが偶数)であるので、予想が成り立つならば、ch1(Kp)=pである。

　　グラフに許される色の数をm、各辺に許される色の数をkとすると、k=pである。

　　m=k+1=p+1の場合を考える。

　　p=1の場合、頂点v1があり、サイズは1(1-1)/2=0である。

　　p=3の場合、頂点v2、v3を加えることを考える。増える辺はp(p-1)/2-(p-2)(p-3)/2=2p-3=6-3=3本である。この辺はv2、v3からv1への各1本とv2とv3を結ぶ1本である。e3,1=(v1、v2)、e3,2=(v1、v3)、e3,3=(v2、v3)とする。

　　　許される色の数はm=p+1=4、k=p=3である。

　　　それぞれの辺が許される色のリストをc3,jで表す。このとき、c3,1、c3,2、c3,3が①すべて同じ、②1つだけ違う、③3つとも違う、の3通りが考えられる。どの場合でも、それぞれの辺に互い異なる色を塗ることができるので、それをe3,1=0、e3,2=1、e3,3=2として本質的に問題ない。

　　p=5の場合、頂点v4、v5を加えることを考える。増える辺の本数は2p-3=10-3=7本である。この7本はv4、v5からv1、v2、v3への各3本とv4とv5を結ぶ1本である。e5,1=(v1、v4)、e5,2=(v2、v4)、e5,3=(v3、v4)、e5,4=(v1、v5)、e5,5=(v2、v5)、e5,6=(v3、v5)

、e5,7=(v4、v5)とする。

　　　許される色の数はm=p+1=6、k=p=5である。

　　　それぞれの辺が許される色のリストをc5,jで表す。これら増える辺の最悪の場合を考える。

　　　e5,1について考える。

　　　e5,1の最悪の場合は、v1に接続する辺で確定している色(0、1)がc5,1に入っている場合である。他の3色は①P=3のときに使われた色が入っている、②p=3のときに使われた色が入っていない、の2通りに分けられる。今②の場合を考える。e5,1をP=3のときに使われていない色で塗り、それを色3として本質的に問題ない。

　　　e5,2について考える。

　　　e5,2の最悪の場合は、v2に接続する辺で確定している色(0、2)とv4に接続している辺で確定している色(3)がc5,2に入っている場合である。他の2色は①P=3のときに使われた色が入っている、②p=3のときに使われた色が入っていない、の2通りに分けられる。今②の場合を考える。e5,2をP=3のときに使われていない色で塗り、それを色4として本質的に問題ない。

　　　e5,3について考える。

　　　e5,3の最悪の場合は、v3に接続する辺で確定している色(1、2)とv4に接続している辺で確定している色(3、4)がc5,3に入っている場合である。他の1色は①P=3のときに使われた色が入っている、②p=3のときに使われた色が入っていない、の2通りに分けられる。今①の場合を考える。そうすると、e5,3は色0で塗られることになる。

--------------------------------------------------------------------------------------------------

　　　e5,4について考える。

　　　e5,4の最悪の場合は、v1に接続する辺で確定している色(0、1、3)がc5,4に入っている場合である。他の2色は①P=3のときに使われた色が入っている、②p=3のときに使われた色が入っていない、の2通りに分けられる。①の場合、色(2、4)、色(2、5)のどちらか、②の場合、色(4、5)である。

　　　今②の場合だったとして、色5をe5,4に塗るとする。

　　　e5,5について考える。

　　　e5,5の最悪の場合は、v2に接続する辺で確定している色(0、2、4)とv5に接続している辺で確定している色(5)がc5,5に入っている場合である。他の1色は①P=3のときに使われた色が入っている、②p=3のときに使われた色が入っていない、の2通りに分けられる。①の場合、色(1)で、②の場合、色(3)である。今、②の場合だったとして、色3をe5,5に塗る。

　　　e5,6について考える。

　　　e5,6の最悪の場合は、v3に接続している辺で確定している色(0、1、2)とv5に接続している辺で確定している色(3、5)がc5,6に入っている場合である。

　　　このとき、c5,6=(0、1、2、3、5)はもうすでに5色許されている。この許されている5色では彩色不可能である。

--------------------------------------------------------------------------------------------------

　　　e5,4に戻って、e5,4を色4で塗るとする。

　　　e5,5について考える。

　　　e5,5の最悪の場合は、v2に接続する辺で確定している色(0、2、4)とv5に接続している辺で確定している色(4)がc5,5に入っている場合である。他の2色は①P=3のときに使われた色が入っている、②p=3のときに使われた色が入っていない、の2通りに分けられる。①の場合(1、3)、(1、5)のどちらかであり、②の場合(3、5)である。

　　　今②の場合だったとして、色3をe5,5に塗る。

　　　e5,6について考える。

　　　e5,6の最悪の場合は、v3に接続している辺で確定している色(0、1、2)とv5に接続している辺で確定している色(3、4)がc5,6に入っている場合である。

　　　このとき、c5,6=(0、1、2、3、4)はもうすでに5色許されている。この許されている5色では彩色不可能である。

--------------------------------------------------------------------------------------------------

　　　e5,5に戻って、e5,5を色5で塗るとする。

　　　e5,6について考える。

　　　e5,6の最悪の場合は、v3に接続している辺で確定している色(0、1、2)とv5に接続している辺で確定している色(4、5)がc5,6に入っている場合である。

　　　このとき、c5,6=(0、1、2、4、5)はもうすでに5色許されている。この許されている5色では彩色不可能である。

--------------------------------------------------------------------------------------------------

　　　これで、完全グラフがp=5のときに5-リスト辺彩色可能ではないことが証明された。

　　　よって、リスト彩色予想は否定される。(証明終わり)