最大度为6的图G的邻点可区别边色数的一个上界

吴燕青

(山西师范大学数学与计算机科学学院,山西临汾 041000)

1 引言

本文主要考虑不含孤立边的有限简单图.对图G,用V(G),E(G),∆(G)和mad(G)分别表示图G的顶点集,边集,最大度和最大平均度.在G中,用NG(v)表示顶点v的邻集.度为k的顶点称为k-顶点.度至少为(至多为)k的顶点称为k+-顶点(k−-顶点).用di(v)表示与顶点v相邻的i-顶点的数目.一个图G称为半正则的,如果它的每一条边至少和一个最大度顶点相关联.否则,称为非半正则的.一个图G的正常边着色是一个映射φ:E(G)→{1,···,k},使得每一对相邻边e1和e2,有φ(e1)(e2).用cφ(v)表示在着色φ下与v相关联的边所着的颜色组成的集合.一个图G的正常边着色φ称为邻点可区别边着色,如果G的任何相邻顶点u和v,满足cφ(u)(v).G的邻点可区别边色数是使得G有一个k-邻点可区别边着色的最少颜色数k.

在2002年,文献[1]首先讨论了邻点可区别边着色问题,并提出了以下猜想.

猜想设图G为顶点数至少为3的连通图且5,则.对于一般图G,文献[2]给出了若∆(G)>1020,则.文献[3]给出了.文献[4]给出了.文献[5]给出了若∆(G)≤3,则.文献[6]给出了若∆(G)≤5且,则.文献[7]给出了若∆(G)≤4,则,和若∆(G)≤5,则.本文证明了若G是一个最大度为6的非半正则图,则.

引理1.1[7]假设G是一个∆(G)≥2的半正则图.若∆(G)≡0(mod 3),则.

2 主要结果

定理2.1设G是一个最大度为6的非半正则图,则.

证假设G是含边数最少的连通的极小反例.由于G是非半正则的,所以存在uv∈E(G),使得dG(u)≤5且dG(v)≤5.不妨设dH(u)≤dH(v).设H=G−uv,由G的极小性可知,H有一个12-邻点可区别边着色φ,它用的颜色集C={1,2,···,12}.为了叙述起来方便,称在φ下边e对颜色α是允许的,若在φ下用颜色α给边e重新着色可得H的一个新的12-邻点可区别边着色.用L(e)表示在φ下由边e的所有允许的颜色组成的集.设xy∈E(H),且dG(x)=dG(y).若颜色β∈cφ(y)cφ(x),且|cφ(y)∩cφ(x)|=dH(x)=dH(y)−1,则称在φ下颜色β为顶点x的不法颜色.用Ax表示在φ下顶点x的所有不法颜色组成的集.设Ωz(x)={cφ(y)|y∈NH(x){z}}(或Ω(x)={cφ(y)|y∈NH(x)}).由uv的选择可知dH(u)+dH(v)≤8.

情形1假设dH(u)+dH(v)≤6.

情形1.1假设dH(u)=0.由uv的选择和G的假设可知1≤dH(v)≤4.显然,存在p∈Ccφ(v),用p给uv着色可得G的一个12-邻点可区别边着色,矛盾.

情形1.2假设dH(u)=1且u0∈NH(u).由uv的选择可知1≤dH(v)≤4.

假设dH(v)=1且v0∈NH(v).若φ(vv0)6φ(uu0),显然,存在p∈C{cφ(v)∪cφ(u)},用p给uv着色可得G的一个12-邻点可区别边着色,矛盾.否则,φ(vv0)=φ(uu0).由于|L(vv0)|≥1,所以存在q∈L(vv0).现用q给vv0重新着色可得H的一个12-邻点可区别边着色φ0.从而φ0(vv0)(uu0),正如前面已讨论,矛盾.

假设2≤dH(v)≤4.显然,存在p∈C{cφ(v)∪cφ(u)},用p给uv着色可得G的一个12-邻点可区别边着色,矛盾.

情形1.3假设dH(u)=2且uj∈NH(u),其中j=1,2.由uv的选择可知2≤dH(v)≤4.

假设dH(v)=2且vj∈NH(v),其中j=1,2. 若|cφ(u)∩cφ(v)|≤1,显然,存在p∈C{cφ(v)∪cφ(u)},用p给uv着色可得G的一个12-邻点可区别边着色,矛盾.否则,|cφ(u)∩cφ(v)|=2.不妨设φ(vv1)=1和φ(vv2)=2.在H中,若v的邻点有一个5−-顶点,不妨设dH(v1)≤5.由于|L(vv1)|≥1,所以存在p∈L(vv1).现用p给vv1重新着色可得H的一个12-邻点可区别边着色φ0.从而|cφ0(u)∩cφ0(v)|=1,正如前面已讨论,矛盾.否则,v1和v2均是6-顶点.设v1j∈NH(v1),其中j=1,2,3,4,5.若2∈cφ(v1),因而|L(vv1)|≥1,所以存在p∈L(vv1).现用p给vv1重新着色可得H的一个12-邻点可区别边着色φ0.从而|cφ0(u)∩cφ0(v)|=1,正如前面已讨论,矛盾.否则,2(v1).不妨设φ(v1v1j)=j+2,其中j=1,2,3,4,5.若存在q∈C{cφ(v)∪cφ(v1)},用q给vv1重新着色可得H的一个12-邻点可区别边着色φ0,从而|cφ0(u)∩cφ0(v)|=1,正如前面已讨论,矛盾.否则,不妨设cφ(v11)={3,4,5,6,7,8},cφ(v12)={3,4,5,6,7,9},cφ(v13)={3,4,5,6,7,10},cφ(v14)={3,4,5,6,7,11}和cφ(v15)={3,4,5,6,7,12}. 若存在r∈{1,2},使得{r,4,5,6,7,8Ωv1(v11),那么用r和3分别给v1v11和vv1重新着色可得H的一个12-邻点可区别边着色φ0.从而|cφ0(u)∩cφ0(v)|=1,正如前面已讨论,矛盾.否则,在φ下,{{1,4,5,6,7,8},{2,4,5,6,7,8}}⊆Ωv1(v11).由于|Ωv1(v11)|=5,所以存在s∈{9,10,11,12},使得{s,4,5,6,7,8Ωv1(v11).现用s和t∈{9,10,11,12}{s},分别给v1v11和vv1重新着色可得H的一个12-邻点可区别边着色φ0.从而|cφ0(u)∩cφ0(v)|=1,正如前面已讨论,矛盾.

假设3≤dH(v)≤4.由前面的讨论可知,uj均是4+-顶点,其中j=1,2.显然,存在p∈C{cφ(v)∪cφ(u)},用p给uv着色可得G的一个12-邻点可区别边着色,矛盾.

情形1.4假设dH(u)=3.因而dH(v)=3.设vj∈NH(v),其中j=1,2,3.

假设|cφ(u)∩cφ(v)|=0.若存在p∈C{cφ(v)∪cφ(u)},用p给uv着色可得G的一个12-邻点可区别边着色,矛盾.否则,在φ下,{{p}∪cφ(v)}∈Ω(v),或{{p}∪cφ(u)}∈Ω(u).由于|L(vv1)|≥5,所以存在q∈L(vv1){cφ(v2)∪cφ(v3)}.现用q给vv1重新着色,用φ(vv1)给uv着色可得G的一个12-邻点可区别边着色,矛盾.

假设1≤|cφ(u)∩cφ(v)|≤2.显然,存在p∈C{cφ(v)∪cφ(u)},用p给uv着色可得G的一个12-邻点可区别边着色,矛盾.

假设|cφ(u)∩cφ(v)|=3.不妨设φ(vvj)=j,其中j=1,2,3.

在H中,假设v的邻点中有一个5−-顶点.不妨设d(v1)≤5.由情形1.3可知,v2和v3均不是3-顶点.显然,|L(vv1)|≥1,所以存在p∈L(vv1),用p给vv1重新着色可得H的一个12-邻点可区别边着色φ0.从而|cφ0(u)∩cφ0(v)|=2,正如前面已讨论,矛盾.

在H中,假设v的邻点均是6-顶点.设v1j∈NH(v1),其中j=1,2,3,4,5.

假设|{2,3}∩cφ(v1)|=0.不妨设φ(v1v1j)=j+3,其中j=1,2,3,4,5.若存在p∈C{cφ(v)∪cφ(v1)},用p给vv1重新着色可得H的一个12-邻点可区别边着色φ0,从而|cφ0(u)∩cφ0(v)|=2,正如前面已讨论,矛盾.否则,不妨设cφ(v11)={4,5,6,7,8,9},cφ(v12)={4,5,6,7,8,10},cφ(v13)={4,5,6,7,8,11}和cφ(v14)={4,5,6,7,8,12}. 若存在q∈{1,2,3},使得{q,5,6,7,8,9Ωv1(v11),那么先用q给v1v11重新着色.进一步,若用4给vv1重新着色可得H的一个12-邻点可区别边着色,从而|cφ0(u)∩cφ0(v)|=2,正如前面已讨论,矛盾.否则,cφ(v15)={q,4,5,6,7,8}.现用10给vv1重新着色可得H的一个12-邻点可区别边着色φ00.从而|cφ00(u)∩cφ00(v)|=2,正如前面已讨论,矛盾.否则,在φ下,{{1,5,6,7,8,9},{2,5,6,7,8,9},{3,5,6,7,8,9}}⊆Ωv1(v11).由于|Ωv1(v11)|=5,所以存在r∈{10,11,12},使得{r,5,6,7,8,9Ωv1(v11).若用r和s∈{10,11,12}{r}分别给v1v11和vv1重新着色可得H的一个12-邻点可区别边着色φ0,从而|cφ0(u)∩cφ0(v)|=2,正如前面已讨论,矛盾.否则,cφ(v5)={r,s,5,6,7,8}.现用r和t∈{10,11,12}{r,s}分别给v1v11和vv1重新着色可得H的一个12-邻点可区别边着色φ00.从而|cφ00(u)∩cφ00(v)|=2,正如前面已讨论,矛盾.

假设|{2,3}∩cφ(v1)|=1.不妨设φ(v1v11)=2,φ(v1v1j)=j+2,其中j=2,3,4,5.若存在p∈C{cφ(v)∪cφ(v1)},用p给vv1重新着色可得H的一个12-邻点可区别边着色φ0,从而|cφ0(u)∩cφ0(v)|=2,正如前面已讨论,矛盾.否则,不妨设cφ(v11)={2,4,5,6,7,8},cφ(v12)={2,4,5,6,7,9},cφ(v13)={2,4,5,6,7,10},cφ(v14)={2,4,5,6,7,11}和cφ(v15)={2,4,5,6,7,12}.若存在q∈{1,3},使得{q,2,5,6,7,9Ωv1(v12),那么用q和4分别给v1v12和vv1重新着色可得H的一个12-邻点可区别边着色φ0.从而|cφ0(u)∩cφ0(v)|=2,正如前面已讨论,矛盾.否则,在φ下,{{1,2,5,6,7,9},{2,3,5,6,7,9}}⊆Ωv1(v12).由于|Ωv1(v12)|=5,所以存在r∈{8,10,11,12},使得{r,2,5,6,7,9Ωv1(v12).现用r和s∈{8,10,11,12}{r}分别给v1v12和vv1重新着色可得H的一个12-邻点可区别边着色φ0.从而|cφ0(u)∩cφ0(v)|=2,正如前面已讨论,矛盾.

假设|{2,3}∩cφ(v1)|=2.由于|L(vv1)|≥1,所以存在p∈L(vv1).现用p给vv1重新着色可得H的一个12-邻点可区别边着色φ0,从而|cφ0(u)∩cφ0(v)|=2,正如前面已讨论,矛盾.

情形2假设dH(u)+dH(v)=7.由uv的选择可知dH(u)=3且dH(v)=4.设uj∈NH(u),其中j=1,2,3.由情形1可知,uj均为5+-顶点,其中j=1,2,3.因此存在p∈C{cφ(u)∪cφ(v)},用p给uv着色可得G的一个12-邻点可区别边着色,矛盾.

情形3假设dH(u)+dH(v)=8.由uv的选择可知dH(u)=4且dH(v)=4.设vi∈NH(v),其中i=1,2,3,4.在φ下,不妨设φ(vvi)=i,其中i=1,2,3,4.设uj∈NH(u),其中j=1,2,3,4.由情形1和2可知,在H中,与u相邻的顶点和与v相邻的顶点均是5+-顶点.

情形3.1假设dH(uj)=6,其中j=1,2,3,4.

情形3.1.1假设|cφ(u)∩cφ(v)|=0.设φ(uuj)=j+4,其中j=1,2,3,4.若存在p∈C{cφ(u)∪cφ(v)},用p给uv着色可得G的一个12-邻点可区别边着色,矛盾.否则,在φ下,{{p}∪cφ(v)}∈Ω(v). 显然,C{cφ(v)∪cφ(u)}={9,10,11,12}. 不妨设cφ(v1)={1,2,3,4,9},cφ(v2)={1,2,3,4,10},cφ(v3)={1,2,3,4,11}和cφ(v4)={1,2,3,4,12}. 若存在q∈{5,6,7,8},使得{q,2,3,4,9Ωv(v1),那么用q给vv1重新着色,用1给uv着色可得G的一个12-邻点可区别边着色,矛盾.否则,在φ下,Ωv(v1)={{2,3,4,5,9},{2,3,4,6,9},{2,3,4,7,9},{2,3,4,8,9}}.现用10给vv1重新着色,用11给uv着色可得G的一个12-邻点可区别边着色,矛盾.

情形3.1.2假设1≤|cφ(u)∩cφ(v)|≤3.显然,存在p∈C{cφ(u)∪cφ(v)},用p给uv着色可得G的一个12-邻点可区别边着色,矛盾.

情形3.1.3假设|cφ(u)∩cφ(v)|=4.

在H中,假设d6(v)=4.因此d(vi)=6,其中i=1,2,3,4.设v1j∈NH(v1){v},其中j=1,2,3,4,5.

假设|{2,3,4}∩cφ(v1)|=0.不妨设φ(v1v1j)=j+4,其中j=1,2,3,4,5.若存在p∈C{cφ(v)∪cφ(v1)},用p给vv1重新着色可得H的一个12-邻点可区别边着色φ0,从而|cφ0(u)∩cφ0(v)|=3,正如情形3.1.2,矛盾.否则,不妨设cφ(v11)={5,6,7,8,9,10},cφ(v12)={5,6,7,8,9,11}和cφ(v13)={5,6,7,8,9,12}.若存在q∈{1,2,3,4},使得{q,6,7,8,9,10}/∈Ωv1(v11),那么先用q给v1v11重新着色.进一步,若用5给vv1重新着色可得H的一个12-邻点可区别边着色φ0,从而|cφ0(u)∩cφ0(v)|=3,正如情形3.1.2,矛盾.否则,cφ(v14)={q,5,6,7,8,9},或cφ(v15)={q,5,6,7,8,9}. 不妨设cφ(v14)={q,5,6,7,8,9}. 若用11给vv1重新着色可得H的一个12-邻点可区别边着色φ00,从而|cφ00(u)∩cφ00(v)|=3,正如情形3.1.2,矛盾.否则,cφ(v15)={q,6,7,8,9,11}.现用12给vv1重新着色可得H的一个12-邻点可区别边着色φ000.从而|cφ000(u)∩cφ000(v)|=3,正如情形3.1.2,矛盾.否则,在φ下,{{1,6,7,8,9,10},{2,6,7,8,9,10},{3,6,7,8,9,10},{4,6,7,8,9,10}}⊆Ωv1(v11).类似的,{{1,5,7,8,9,11},{2,5,7,8,9,11},{3,5,7,8,9,11},{4,5,7,8,9,11}}⊆Ωv1(v12).由于|Ωv1(v1j)|=5,其中j=1,2,所以存在r∈{11,12},不妨设r=11,使得{6,7,8,9,10,11}/∈Ωv1(v11),存在s∈{10,12},使得{s,5,7,8,9,11Ωv1(v12).若用11和12分别给v1v11和vv1重新着色可得H的一个12-邻点可区别边着色φ0,从而|cφ0(u)∩cφ0(v)|=3,正如情形3.1.2,矛盾.否则,cφ(v14)={6,7,8,9,11,12},或cφ(v15)={6,7,8,9,11,12}.不妨设cφ(v14)={6,7,8,9,11,12}.若用s和t∈{10,12}{s}分别给v1v12和vv1重新着色可得H的一个12-邻点可区别边着色φ00,从而|cφ00(u)∩cφ00(v)|=3,正如情形3.1.2,矛盾.否则,cφ(v15)={5,7,8,9,10,12}.现用11,s和t分别给v1v11,v1v12和vv1重新着色可得H的一个12-邻点可区别边着色φ000.从而|cφ000(u)∩cφ000(v)|=3,正如情形3.1.2,矛盾.

假设|{2,3,4}∩cφ(v1)|=1.不妨设φ(v1v11)=2和φ(v1v1j)=j+3,其中j=2,3,4,5.若存在p∈C{cφ(v)∪cφ(v1)},用p给vv1重新着色可得H的一个12-邻点可区别边着色φ0,从而|cφ0(u)∩cφ0(v)|=3,正如情形3.1.2,矛盾. 否则,不妨设cφ(v11)={2,5,6,7,8,9},cφ(v12)={2,5,6,7,8,10},cφ(v13)={2,5,6,7,8,11}和cφ(v14)={2,5,6,7,8,12}. 若存在q∈{1,3,4},使得{q,2,6,7,8,10Ωv1(v12),那么先用q给v1v12重新着色.进一步,若用5给vv1重新着色可得H的一个12-邻点可区别边着色φ0,从而|cφ0(u)∩cφ0(v)|=3,正如情形3.1.2,矛盾.否则,cφ(v15)={q,2,5,6,7,8}.现用11给vv1重新着色可得H的一个12-邻点可区别边着色φ00.从而|cφ00(u)∩cφ00(v)|=3,正如情形3.1.2,矛盾.否则,在φ下,{{1,2,6,7,8,10},{2,3,6,7,8,10},{2,4,6,7,8,10}}⊆Ωv1(v12).由于|Ωv1(v12)|=5,所以存在r∈{9,11,12},使得{r,2,6,7,8,10Ωv1(v12),那么先用r给v1v12重新着色.进一步,若用s∈{9,11,12}{r}给vv1重新着色可得H的一个12-邻点可区别边着色φ0,从而|cφ0(u)∩cφ0(v)|=3,正如情形3.1.2,矛盾. 否则,cφ(v15)={r,s,2,6,7,8}. 现用t∈{9,11,12}{r,s}给vv1重新着色可得H的一个12-邻点可区别边着色φ00.从而|cφ00(u)∩cφ00(v)|=3,正如情形3.1.2,矛盾.

假设|{2,3,4}∩cφ(v1)|=2.不妨设φ(v1v11)=2,φ(v1v12)=3和φ(v1v1j)=j+2,其中j=3,4,5.若存在p∈C{cφ(v)∪cφ(v1)},用p给vv1重新着色可得H的一个12-邻点可区别边着色φ0,从而|cφ0(u)∩cφ0(v)|=3,正如情形3.1.2,矛盾.否则,不妨设cφ(v11)={2,3,5,6,7,8},cφ(v12)={2,3,5,6,7,9},cφ(v13)={2,3,5,6,7,10},cφ(v14)={2,3,5,6,7,11}和cφ(v15)={2,3,5,6,7,12}.若存在q∈{1,4},使得{q,2,3,6,7,10}/∈Ωv1(v13),那么用q和5分别给v1v13和vv1重新着色可得H的一个12-邻点可区别边着色φ0.从而|cφ0(u)∩cφ0(v)|=3,正如情形3.1.2,矛盾.否则,在φ下,{{1,2,3,6,7,10},{2,3,4,6,7,10}}⊆Ωv1(v13).由于|Ωv1(v13)|=5,所以存在r∈{8,9,11,12},使得{r,2,3,6,7,10Ωv1(v13).现用r和s∈{8,9,11,12}{r}分别给v1v13和vv1重新着色可得H的一个12-邻点可区别边着色φ0,从而|cφ0(u)∩cφ0(v)|=3,正如情形3.1.2,矛盾.

假设|{2,3,4}∩cφ(v1)|=3.由于|L(vv1)|≥1,所以存在p∈L(vv1).现用p给vv1重新着色可得H的一个12-邻点可区别边着色φ0.从而|cφ0(u)∩cφ0(v)|=3,正如情形3.1.2,矛盾.

在H中,假设d6(v)≤3.不妨设d(v1)=5.若|{2,3,4}∩cφ(v1)|≥1,因而|L(vv1)|≥1,所以存在p∈L(vv1).现用p给vv1重新着色可得H的一个12-邻点可区别边着色φ0.从而|cφ0(u)∩cφ0(v)|=3,正如情形3.1.2,矛盾.否则,|{2,3,4}∩cφ(v1)|=0.不妨设φ(v1v1j)=j+4,其中j=1,2,3,4.若存在q∈C{cφ(v)∪cφ(v1)},用q给vv1重新着色可得H的一个12-邻点可区别边着色φ0,从而|cφ0(u)∩cφ0(v)|=3,正如情形3.1.2,矛盾.否则,不妨设cφ(v11)={5,6,7,8,9},cφ(v12)={5,6,7,8,10},cφ(v13)={5,6,7,8,11}和cφ(v14)={5,6,7,8,12}. 若存在r∈{1,2,3,4},使得{r,6,7,8,9Ωv1(v11),那么用r和5分别给v1v11和vv1重新着色可得H的一个12-邻点可区别边着色φ0.从而|cφ0(u)∩cφ0(v)|=3,正如情形3.1.2,矛盾.否则,在φ下,Ωv1(v11)={{1,6,7,8,9},{2,6,7,8,9},{3,6,7,8,9},{4,6,7,8,9}}.现用10和11分别给v1v11和vv1重新着色可得H的一个12-邻点可区别边着色φ0.从而|cφ0(u)∩cφ0(v)|=3,正如情形3.1.2,矛盾.

情形3.2假设dH(u1)=5,且d(uj)=6,其中j=2,3,4.

情形3.2.1假设|cφ(u)∩cφ(v)|=0.

不妨设φ(uuj)=j+4,j=1,2,3,4.若存在p∈C{cφ(v)∪cφ(u)},用p给uv着色可得G的一个12-邻点可区别边着色,矛盾.否则,在φ下,{{p}∪cφ(v)}∈Ω(v),或{{p}∪cφ(u)}∈Ω(u).显然,C{cφ(v)∪cφ(u)}={9,10,11,12}.

假设|Av∩{9,10,11,12}|=4. 不妨设cφ(v1)={1,2,3,4,9},cφ(v2)={1,2,3,4,10},cφ(v3)={1,2,3,4,11}和cφ(v4)={1,2,3,4,12}.若存在q∈{5,6,7,8},使得{q,2,3,4,9Ωv(v1),那么先用q给vv1重新着色.进一步,若用1给uv着色可得G的一个12-邻点可区别边着色,矛盾.否则,cφ(u1)={1,5,6,7,8}.现用10给uv着色可得G的一个12-邻点可区别边着色,矛盾.否则,在φ下,Ωv(v1)={{2,3,4,5,9},{2,3,4,6,9},{2,3,4,7,9},{2,3,4,8,9}}.先用10给vv1重新着色.进一步,若用11给uv着色可得G的一个12-邻点可区别边着色,矛盾.否则,cφ(u1)={5,6,7,8,11}.现用12给uv着色可得G的一个12-邻点可区别边着色,矛盾.

假设|Av∩{9,10,11,12}|=3. 因而|Au∩{9,10,11,12}|=1. 不妨设cφ(v1)={1,2,3,4,9},cφ(v2)={1,2,3,4,10},cφ(v3)={1,2,3,4,11}和cφ(u1)={5,6,7,8,12}.由于|L(uu1)|≥3,所以存在q∈L(uu1).若用q给uu1重新着色,用5给uv着色可得G的一个12-邻点可区别边着色,矛盾.否则,cφ(v4)={1,2,3,4,5}.由于|Ωv(v1)|=4,所以存在r∈{5,6,7,8,12},使得{r,2,3,4,9Ωv(v1).现用r给vv1重新着色,用10给uv着色可得G的一个12-邻点可区别边着色,矛盾.

情形3.2.2假设|cφ(u)∩cφ(v)|=1. 不妨设φ(uu1)=1和φ(uuj)=j+3,其中j=2,3,4.若存在p∈C{cφ(v)∪cφ(u)},用p给uv着色可得G的一个12-邻点可区别边着色,矛盾.否则,在φ下,{{p}∪cφ(v)}∈Ω(v)或{{p}∪cφ(u)}∈Ω(u).显然,C{cφ(v)∪cφ(u)}={8,9,10,11,12}. 不妨设cφ(v1)={1,2,3,4,8},cφ(v2)={1,2,3,4,9},cφ(v3)={1,2,3,4,10},cφ(v4)={1,2,3,4,11}和cφ(u1)={1,5,6,7,12}. 若存在q∈{5,6,7,12},使得{q,1,3,4,9Ωv(v2),那么用q给vv2重新着色,用2给uv着色可得G的一个12-邻点可区别边着色,矛盾.否则,在φ下,Ωv(v2)={{1,3,4,5,9},{1,3,4,6,9},{1,3,4,7,9},{1,3,4,9,12}}.现用10给vv2重新着色,用11给uv着色可得G的一个12-邻点可区别边着色,矛盾.

情形3.2.3假设2≤|cφ(u)∩cφ(v)|≤3.显然,存在p∈C{cφ(v)∪cφ(u)},用p给uv着色可得G的一个12-邻点可区别边着色,矛盾.

情形3.2.4假设|cφ(u)∩cφ(v)|=4.设φ(uuj)=j,其中j=1,2,3,4.

假设|{2,3,4}∩cφ(u1)|≥1.由于|L(uu1)|≥1,所以存在p∈L(uu1).现用p给uu1重新着色可得H的一个12-邻点可区别边着色φ0.从而|cφ0(u)∩cφ0(v)|=3,正如情形3.2.3,矛盾.假设|{2,3,4}∩cφ(u1)|=0.设u1j∈NH(u1){u},其中j=1,2,3,4.不妨设φ(u1u1j)=j+4,其中j=1,2,3,4.若存在q∈C{cφ(u)∪cφ(u1)},用q给uu1重新着色可得H的一个12-邻点可区别边着色φ0,从而|cφ0(u)∩cφ0(v)|=3,正如情形3.2.3,矛盾.否则,不妨设cφ(u11)={5,6,7,8,9},cφ(u12)={5,6,7,8,10},cφ(u13)={5,6,7,8,11}和cφ(u14)={5,6,7,8,12}.若存在r∈{1,2,3,4},使得{r,6,7,8,9Ωu1(u11),那么用r和5分别给u1u11和uu1重新着色可得H的一个12-邻点可区别边着色φ0.从而|cφ0(u)∩cφ0(v)|=3,正如情形3.2.3,矛盾.否则,在φ下,Ωu1(u11)={{1,6,7,8,9},{2,6,7,8,9},{3,6,7,8,9},{4,6,7,8,9}}.现用10和11分别给u1u11和uu1重新着色可得H的一个12-邻点可区别边着色φ0.从而|cφ0(u)∩cφ0(v)|=3,正如情形3.2.3,矛盾.

情形3.3假设dH(u1)=dH(u2)=5且dH(u3)=dH(u4)=6.

情形3.3.1假设|cφ(u)∩cφ(v)|=0.不妨设φ(uuj)=j+4,j=1,2,3,4.若存在p∈C{cφ(v)∪cφ(u)},用p给uv着色可得G的一个12-邻点可区别边着色,矛盾.否则,在φ下,{{p}∪cφ(v)}∈Ω(v),或{{p}∪cφ(u)}∈Ω(u).显然,C{cφ(v)∪cφ(u)}={9,10,11,12}.

假设|Av∩{9,10,11,12}|=4. 不妨设cφ(v1)={1,2,3,4,9},cφ(v2)={1,2,3,4,10},cφ(v3)={1,2,3,4,11}和cφ(v4)={1,2,3,4,12}.若存在q∈{5,6,7,8},使得{q,2,3,4,9}/∈Ωv(v1),那么先用q给vv1重新着色.进一步,若用1给uv着色可得G的一个12-邻点可区别边着色,矛盾.否则,cφ(u1)={1,5,6,7,8}或cφ(u2)={1,5,6,7,8}.不妨设cφ(u1)={1,5,6,7,8}.若用10给uv着色可得G的一个12-邻点可区别边着色,矛盾.否则,cφ(u2)={5,6,7,8,10}.现用11给uv着色可得G的一个12-邻点可区别边着色,矛盾.否则,在φ下,Ωv(v1)={{2,3,4,5,9},{2,3,4,6,9},{2,3,4,7,9},{2,3,4,8,9}}.类似的,Ωv(v2)={{1,3,4,5,10},{1,3,4,6,10},{1,3,4,7,10},{1,3,4,8,10}}.先用10和11分别给vv1和vv2重新着色.进一步,若用2给uv着色可得G的一个12-邻点可区别边着色,矛盾.否则,cφ(u1)={2,5,6,7,8}或cφ(u2)={2,5,6,7,8}. 不妨设cφ(u1)={2,5,6,7,8}. 若用 9给uv着色可得G的一个12-邻点可区别边着色,矛盾.否则,cφ(u2)={5,6,7,8,9}.现用12给uv着色可得G的一个12-邻点可区别边着色,矛盾.

假设|Av∩{9,10,11,12}|=3. 因而|Au∩{9,10,11,12}|≥1. 不妨设cφ(v1)={1,2,3,4,9},cφ(v2)={1,2,3,4,10},cφ(v3)={1,2,3,4,11}和cφ(u1)={5,6,7,8,12}.由于|L(uu1)|≥3,所以存在q∈L(uu1).若用q给uu1重新着色,用5给uv着色可得G的一个12-邻点可区别边着色,矛盾.否则,cφ(u2)={q,5,6,7,8}或cφ(v4)={1,2,3,4,5}.若cφ(v4)={1,2,3,4,5},显然,存在r∈{5,6,7,8,12},使得{r,2,3,4,9Ωv(v1),那么先用r给vv1重新着色.进一步,若用10给uv着色可得G的一个12-邻点可区别边着色,矛盾.否则,cφ(u2)={5,6,7,8,10}.现用11给uv着色可得G的一个12-邻点可区别边着色,矛盾.若cφ(u2)={q,5,6,7,8},由于|L(uu2)|≥3,所以存在s∈L(uu2)cφ(u1).现用s给uu2重新着色,用12给uv着色可得G的一个12-邻点可区别边着色,矛盾.

假设|Av∩{9,10,11,12}|=2. 因而|Au∩{9,10,11,12}|=2. 不妨设cφ(v1)={1,2,3,4,9},cφ(v2)={1,2,3,4,10},cφ(u1)={5,6,7,8,11}和c(u2)={5,6,7,8,12}. 由于|L(uu1)|≥3,所以存在q∈L(uu1)cφ(u2).现用q给uu1重新着色,用12给uv着色可得G的一个12-邻点可区别边着色,矛盾.

情形3.3.2假设|cφ(u)∩cφ(v)|=1.

不妨设φ(uu1)=1和φ(uuj)=j+3,其中j=2,3,4.若存在p∈C{cφ(v)∪cφ(u)},用p给uv着色可得G的一个12-邻点可区别边着色,矛盾.否则,在φ下,{{p}∪cφ(v)}∈Ω(v),或{{p}∪cφ(u)}∈Ω(u).显然,C{cφ(v)∪cφ(u)}={8,9,10,11,12}.

假设|Av∩{8,9,10,11,12}|=4.因而|Au∩{8,9,10,11,12}|≥1.不妨设cφ(v1)={1,2,3,4,8},cφ(v2)={1,2,3,4,9},cφ(v3)={1,2,3,4,10},cφ(v4)={1,2,3,4,11}和cφ(u1)={1,5,6,7,12}.若存在q∈{5,6,7,12},使得{q,1,3,4,9Ωv(v2),那么先用q给vv2重新着色.进一步,若用2给uv着色可得G的一个12-邻点可区别边着色,矛盾.否则,cφ(u2)={1,2,5,6,7}.现用10给uv着色可得G的一个12-邻点可区别边着色,矛盾.否则,在φ下,Ωv(v2)={{1,3,4,5,9},{1,3,4,6,9},{1,3,4,7,9},{1,3,4,9,12}}.先用10给vv2重新着色.进一步,若用8给uv着色可得G的一个12-邻点可区别边着色,矛盾.否则,cφ(u2)={1,5,6,7,8}.现用11给uv着色可得G的一个12-邻点可区别边着色,矛盾.

假设|Av∩{8,9,10,11,12}|=3.因而|Au∩{8,9,10,11,12}|=2.不妨设cφ(v1)={1,2,3,4,8},cφ(v2)={1,2,3,4,9},cφ(v3)={1,2,3,4,10},cφ(u1)={1,5,6,7,11}和cφ(u2)={1,5,6,7,12}.由于|L(uu2)|≥3,所以存在q∈L(uu2)cφ(u1).现用q给uu2重新着色,用11给uv着色可得G的一个12-邻点可区别边着色,矛盾.

情形3.3.3假设|cφ(u)∩cφ(v)|=2.

不妨设φ(uu1)=1,φ(uu2)=2,φ(uu3)=5 和φ(uu4)=6. 若存在p∈C{cφ(v)∪cφ(u)},用p给uv着色可得G的一个12-邻点可区别边着色,矛盾.否则,在φ下,{{p}∪cφ(v)}∈Ω(v)或{{p}∪cφ(u)}∈Ω(u).显然,C{cφ(v)∪cφ(u)}={7,8,9,10,11,12}.不妨设cφ(v1)={1,2,3,4,7},cφ(v2)={1,2,3,4,8},cφ(v3)={1,2,3,4,9},cφ(v4)={1,2,3,4,10},cφ(u1)={1,2,5,6,11}和cφ(u2)={1,2,5,6,12}. 由于|L(uu1)|≥3,所以存在q∈L(uu1)cφ(u2).现用q给uu1重新着色,用12给uv着色可得G的一个12-邻点可区别边着色,矛盾.

情形3.3.4假设|cφ(u)∩cφ(v)|=3.显然,存在p∈C{cφ(v)∪cφ(u)},用p给uv着色可得G的一个12-邻点可区别边着色,矛盾.

情形3.3.5假设|cφ(u)∩cφ(v)|=4.与情形3.2.4类似,矛盾.

情形3.4假设d(uj)=5,其中j=1,2,3,且d(u4)=6.

情形3.4.1假设|cφ(u)∩cφ(v)|=0.

不妨设φ(uuj)=j+4,j=1,2,3,4.若存在p∈C{cφ(v)∪cφ(u)},用p给uv着色可得G的一个12-邻点可区别边着色,矛盾.否则,在φ下,{{p}∪cφ(v)}∈Ω(v)或{{p}∪cφ(u)}∈Ω(u).显然,C{cφ(v)∪cφ(u)}={9,10,11,12}.

假设|Av∩{9,10,11,12}|=4. 不妨设cφ(v1)={1,2,3,4,9},cφ(v2)={1,2,3,4,10},cφ(v3)={1,2,3,4,11}和cφ(v4)={1,2,3,4,12}.若存在q∈{5,6,7,8},使得{q,2,3,4,9Ωv(v1),那么先用q给vv1重新着色.进一步,若用1给uv着色可得G的一个12-邻点可区别边着色,矛盾.否则,cφ(u1)={1,5,6,7,8}或cφ(u2)={1,5,6,7,8}或cφ(u3)={1,5,6,7,8}.不妨设cφ(u1)={1,5,6,7,8}.若用10给uv着色可得G的一个12-邻点可区别边着色,矛盾.否则,cφ(u2)={5,6,7,8,10}或cφ(u3)={5,6,7,8,10}.不妨设cφ(u2)={5,6,7,8,10}.若用11给uv着色可得G的一个12-邻点可区别边着色,矛盾.否则,cφ(u3)={5,6,7,8,11}.现用12给uv着色可得G的一个12-邻点可区别边着色,矛盾.否则,在φ下,Ωv(v1)={{2,3,4,5,9},{2,3,4,6,9},{2,3,4,7,9},{2,3,4,8,9}}.类似的,Ωv(v2)={{1,3,4,5,10},{1,3,4,6,10},{1,3,4,7,10},{1,3,4,8,10}},Ωv(v3)={{1,2,4,5,11},{1,2,4,6,11},{1,2,4,7,11},{1,2,4,8,11}}和Ωv(v4)={{1,2,3,5,12},{1,2,3,6,12},{1,2,3,7,12},{1,2,3,8,12}}.先用10,11,12和9分别给vv1,vv2,vv3和vv4重新着色.进一步,若用1给uv着色可得G的一个12-邻点可区别边着色,矛盾.否则,cφ(u1)={1,5,6,7,8}或cφ(u2)={1,5,6,7,8}或cφ(u3)={1,5,6,7,8}. 不妨设cφ(u1)={1,5,6,7,8}.若用2给uv着色可得G的一个12-邻点可区别边着色,矛盾.否则,cφ(u2)={2,5,6,7,8}或cφ(u3)={2,5,6,7,8}. 不妨设cφ(u2)={2,5,6,7,8}. 若用 3给uv着色可得G的一个12-邻点可区别边着色,矛盾.否则,cφ(u3)={3,5,6,7,8}.现用4给uv着色可得G的一个12-邻点可区别边着色,矛盾.

假设|Av∩{9,10,11,12}|=3. 因而|Au∩{9,10,11,12}|≥1. 不妨设cφ(v1)={1,2,3,4,9},cφ(v2)={1,2,3,4,10},cφ(v3)={1,2,3,4,11}和cφ(u1)={5,6,7,8,12}.由于|L(uu1)|≥3,所以存在q∈L(uu1).若用q给uu1重新着色,用5给uv着色可得G的一个12-邻点可区别边着色,矛盾.否则,cφ(u2)={q,5,6,7,8}或cφ(u3)={q,5,6,7,8}或cφ(v4)={1,2,3,4,5}. 若cφ(v4)={1,2,3,4,5},显然,存在r∈{5,6,7,8,12},使得{r,2,3,4,9Ωv(v1),那么先用r给vv1重新着色.进一步,若用10给uv着色可得G的一个12-邻点可区别边着色,矛盾.否则,cφ(u2)={5,6,7,8,10}或cφ(u3)={5,6,7,8,10}.不妨设cφ(u2)={5,6,7,8,10}.若用11给uv着色可得G的一个12-邻点可区别边着色,矛盾.否则,cφ(u3)={5,6,7,8,11}.显然存在s∈{6,7}{r},不妨设s=7.由于|L(uu3)|≥3,所以存在t∈L(uu3){cφ(u1)∪cφ(u2)}.现用t给uu3重新着色,用7给uv着色可得G的一个12-邻点可区别边着色,矛盾.若cφ(u2)={q,5,6,7,8}或cφ(u3)={q,5,6,7,8},不妨设cφ(u2)={q,5,6,7,8}.由于|L(uu2)|≥3,所以存在r∈L(uu2)cφ(u1).若用r给uu2重新着色,用12给uv着色可得G的一个12-邻点可区别边着色,矛盾.否则,cφ(u3)={r,5,7,8,12}.由于|L(uu3)|≥2,所以存在s∈L(uu3).显然,(u1),6(u3)和12(u2).因而用s给uu3重新着色,用12给uv着色可得G的一个12-邻点可区别边着色,矛盾.

假设|Av∩{9,10,11,12}|=2.因而|Au∩{9,10,11,12}|≥2.不妨设cφ(v1)={1,2,3,4,9},cφ(v2)={1,2,3,4,10},cφ(u1)={5,6,7,8,11}和cφ(u2)={5,6,7,8,12}. 由于|L(uu1)|≥3,所以存在q∈L(uu1)cφ(u2).若用q给uu1重新着色,用12给uv着色可得G的一个12-邻点可区别边着色,矛盾.否则,cφ(u3)={q,6,7,8,12}.由于|L(uu2)|≥3,所以存在r∈L(uu2){cφ(u1)∪cφ(u3)}.现用r给uu2重新着色,用11给uv着色可得G的一个12-邻点可区别边着色,矛盾.

假设|Av∩{9,10,11,12}|=1.因而|Au∩{9,10,11,12}|=3.不妨设cφ(v1)={1,2,3,4,9},cφ(u1)={5,6,7,8,10},cφ(u2)={5,6,7,8,11}和cφ(u3)={5,6,7,8,12}. 由于|L(uu1)|≥3,所以存在q∈L(uu1){cφ(u2)∪cφ(u3)}.现用q给uu1重新着色,用11给uv着色可得G的一个12-邻点可区别边着色,矛盾.

情形3.4.2假设|cφ(u)∩cφ(v)|=1.

不妨设φ(uu1)=1,φ(uuj)=j+3,j=2,3,4.若存在p∈C{cφ(v)∪cφ(u)},用p给uv着色可得G的一个12-邻点可区别边着色,矛盾.否则,在φ下,{{p}∪cφ(v)}∈Ω(v)或{{p}∪cφ(u)}∈Ω(u).显然,C{cφ(v)∪cφ(u)}={8,9,10,11,12}.

假设|Av∩{8,9,10,11,12}|=4.因而|Au∩{8,9,10,11,12}|≥1.不妨设cφ(v1)={1,2,3,4,8},cφ(v2)={1,2,3,4,9},cφ(v3)={1,2,3,4,10},cφ(v4)={1,2,3,4,11}和cφ(u1)={1,5,6,7,12}.若存在q∈{5,6,7,12},使得{q,1,3,4,9Ωv(v2),那么先用q给vv2重新着色.进一步,若用2给uv着色可得G的一个12-邻点可区别边着色,矛盾. 否则,cφ(u2)={1,2,5,6,7}或cφ(u3)={1,2,5,6,7}. 不妨设cφ(u2)={1,2,5,6,7}.若用8给uv着色可得G的一个12-邻点可区别边着色,矛盾.否则,cφ(u3)={1,5,6,7,8}.现用10给uv着色可得G的一个12-邻点可区别边着色,矛盾.否则,在φ下,Ωv(v2)={{1,3,4,5,9},{1,3,4,6,9},{1,3,4,7,9},{1,3,4,9,12}}.类似的,Ωv(v3)={{1,2,4,5,10},{1,2,4,6,10},{1,2,4,7,10},{1,2,4,10,12}}和 Ωv(v4)={{1,2,3,5,11},{1,2,3,6,11},{1,2,3,7,11},{1,2,3,11,12}}.先用10,11和9分别给vv2,vv3和vv4重新着色.进一步,若用2给uv着色可得G的一个12-邻点可区别边着色,矛盾.否则,cφ(u2)={1,2,5,6,7}或cφ(u3)={1,2,5,6,7}. 不妨设cφ(u2)={1,2,5,6,7}.若用 3给uv着色可得G的一个12-邻点可区别边着色,矛盾.否则,cφ(u3)={1,3,5,6,7}.现用4给uv着色可得G的一个12-邻点可区别边着色,矛盾.

假设|Av∩{8,9,10,11,12}|=3.因而|Au∩{8,9,10,11,12}|≥2.不妨设cφ(v1)={1,2,3,4,8},cφ(v2)={1,2,3,4,9},cφ(v3)={1,2,3,4,10},cφ(u1)={1,5,6,7,11}和cφ(u2)={1,5,6,7,12}.由于|L(uu1)|≥3,所以存在q∈L(uu1)cφ(u2).若用q给uu1重新着色,用12给uv着色可得G的一个12-邻点可区别边着色,矛盾.否则,cφ(u3)={q,5,6,7,12}.由于|L(uu2)|≥3,所以存在r∈L(uu2){cφ(u1)∪cφ(u3)}.现用r给uu2重新着色,用11给uv着色可得G的一个12-邻点可区别边着色,矛盾.

假设|Av∩{8,9,10,11,12}|=2.因而|Au∩{8,9,10,11,12}|=3.不妨设cφ(v1)={1,2,3,4,8},cφ(v2)={1,2,3,4,9},cφ(u1)={1,5,6,7,10},cφ(u2)={1,5,6,7,11}和cφ(u3)={1,5,6,7,12}. 由于|L(uu2)|≥3,所以存在q∈L(uu2){cφ(u1)∪cφ(u3)}. 现用q给uu2重新着色,用12给uv着色可得G的一个12-邻点可区别边着色,矛盾.

情形3.4.3假设|cφ(u)∩cφ(v)|=2.

不妨设φ(uu1)=1,φ(uu2)=2,φ(uu3)=5 和φ(uu4)=6. 若存在p∈C{cφ(v)∪cφ(u)},用p给uv着色可得G的一个12-邻点可区别边着色,矛盾.否则,在φ下,{{p}∪cφ(v)}∈Ω(v)或{{p}∪cφ(u)}∈Ω(u).显然,C{cφ(v)∪cφ(u)}={7,8,9,10,11,12}.

假设|Av∩{7,8,9,10,11,12}|=4.因而|Au∩{7,8,9,10,11,12}|≥2.不妨设cφ(v1)={1,2,3,4,7},cφ(v2)={1,2,3,4,8},cφ(v3)={1,2,3,4,9},cφ(v4)={1,2,3,4,10},cφ(u1)={1,2,5,6,11}和cφ(u2)={1,2,5,6,12}.由于|L(uu1)|≥3,所以存在q∈L(uu1)cφ(u2).若用q给uu1重新着色,用12给uv着色可得G的一个12-邻点可区别边着色,矛盾.否则,cφ(u3)={q,2,5,6,12}.由于|L(uu2)|≥3,所以存在r∈L(uu2){cφ(u1)∪cφ(u3)}.现用r给uu2重新着色,用11给uv着色可得G的一个12-邻点可区别边着色,矛盾.

假设|Av∩{7,8,9,10,11,12}|=3.因而|Au∩{7,8,9,10,11,12}|=3.不妨设cφ(v1)={1,2,3,4,7},cφ(v2)={1,2,3,4,8},cφ(v3)={1,2,3,4,9},cφ(u1)={1,2,5,6,10},cφ(u2)={1,2,5,6,11}和cφ(u3)={1,2,5,6,12}.由于|L(uu3)|≥3,所以存在q∈L(uu3){cφ(u1)∪cφ(u2)}.现用q给uu3重新着色,用10给uv着色可得G的一个12-邻点可区别边着色,矛盾.

情形3.4.4假设|cφ(u)∩cφ(v)|=3.

不妨设φ(uuj)=j,其中j=1,2,3.设φ(uu4)=5.若存在p∈C{cφ(v)∪cφ(u)},用p给uv着色可得G的一个12-邻点可区别边着色,矛盾.否则,在φ下,{{p}∪cφ(v)}∈Ω(v)或{{p}∪cφ(u)}∈Ω(u). 显然,C{cφ(v)∪cφ(u)}={6,7,8,9,10,11,12}. 不妨设cφ(v1)={1,2,3,4,6},cφ(v2)={1,2,3,4,7},cφ(v3)={1,2,3,4,8},cφ(v4)={1,2,3,4,9},cφ(u1)={1,2,3,5,10},cφ(u2)={1,2,3,5,11}和cφ(u3)={1,2,3,5,12}.由于|L(uu1)|≥3,所以存在q∈L(uu1){cφ(u2)∪cφ(u3)}.现用q给uu1重新着色,用11给uv着色可得G的一个12邻点可区别边着色,矛盾.

情形3.4.5假设|cφ(u)∩cφ(v)|=4.与情形3.2.4类似,矛盾.

情形3.5假设d(uj)=5,其中j=1,2,3,4.由于G是最大度为6的连通图,所以在G中存在一个6-顶点w,和一条最短路p=w0,w1,···,wt,其中w0=u,wt=w.设ws是这条路上的第一个6-顶点.根据情形1,2和3.1–3.4可知d(wk)=5且s≥3,其中k=0,1,···,s−1.因此找到了一个5-顶点ws−1和一个6-顶点ws相邻.令H=G−ws−2ws−1.正如前面已讨论,矛盾.因此这个定理成立.

推论2.1设G是一个最大度为6的图,则.

证由引理1.1和定理2.1可得.