稀疏图平方图的染色数上界

2022-01-10 来源：汇智旅游网

第58卷第3期 2020年5月

)JournalofJilinUniversitScienceEditiony(

吉林大学学报(理学版)

Vol.58 No.3

Ma 2020y

:/doi10.13413.cnki.dxblxb.2019315jj

稀疏图平方图的染色数上界

()天津大学应用数学中心,天津300072

张艳

方法证明:如果mad(G)<4且Δ(G)≥7,则χ(G2)≤3Δ(G)+1;如果mad(G)≤4且Δ(G)≥8,则χ(G2)≤3Δ(G)+5.关键词:顶点染色;平方图;最大平均度;色数k-()中图分类号:O157.5 文献标志码:A 文章编号:1671-5489202003-0575-15

,并且u摘要:图G的平方G2定义为顶点集V(当且仅当u和v之间的G)=V(G2)v∈E(G2)距离至多为2.是指使得G2存在正常kG2的色数χ(G2)-顶点染色的最小整数k.用权转移的

UerBoundonChromaticNumberofSuareGrahofSarseGrahsppqppp

(CenterorAliedMathematics,TianinUniversitTianin300072,China)fppjy,jZHANGYan

:AbstractThesuareG2ofagrahGisagrahsuchthatV(G)=V(G2)anduv∈E(G2)ifandonlifqppythedistancebetweenuandvisatmosttwo.ThechromaticnumberG2)ofG2istheminimumkforχ(3Δ(G)+5.

:;;Kewordskvertexcolorinsuaregrah;maximumaveraedereechromaticnumbergqpggy--,whichG2hasaproerkvertexcolorin.Usinhedischarinethodtheauthorprovesthatifpggtggm--((madG)<4andΔ(G)≥7,thenχ(G2)≤3Δ(G)+1,ifmadG)≤4andΔ(G)≥8,thenχ(G2)≤

1 引言与主要结果

边集、顶点集和最大度.用d-点、d--点和d+-点分别表示度数为d的点、度数不大于d的点和度数

,本文所考虑的图均为有限的简单无向图.对于一个图G,用E(和Δ(分别表示图G的G)V(G)G)

…,;如果当u~(,不小于d的点.图G的k-顶点染色是指映射c:V(G)→{1,2,k}v时,有cu)≠c(v)

,并且u则称染色c是正常的[当且仅当u.图G的平方G2定义为:顶点集V(G)=V(G2)v∈E(G2)

和v之间的距离至多为2.平方图G2的色数是指使得G2存在正常k表-染色的最小整数k,用χ(G2)

2]示.根据定义,有χ(是指图G的最大度[研究了平面图的相关G2)≥Δ(G)+1,其中Δ(G).文献[3]性质.

[]4

猜想1 如果G是一个平面图,则:

)当Δ(1G)=3时,有χ(G2)≤7;)当4≤Δ(2G)≤7时,有χ(G2)≤Δ(G)+5;

3Δ(G))当Δ(3G)≥8时,有χ(G2)≤⌊+1.

收稿日期:2019-08-29.

,女,汉族,硕士研究生,从事图论的研究,:m作者简介:张艳(1995—)E-mailathzhanan@tu.edu.cn.gyj)基金项目:国家自然科学基金(批准号:11601380.

[]

的上界是紧的,并且如果Δ(Wener4证明了如果猜想1是正确的,则χ(G2)G)=3,则g

]证明了猜想1.但在平面图中,该猜想未得到验证.G2)≤8.对于超平面图,文献[5χ(

2E(H),(H⊆G,madG)ax=m

V(H)其中V(和E(分别指子图H的顶点集和边集.H)H)

图G的最大平均度定义如下:

{}

()1

10)如果m(1adG)<,则χ(G2)≤Δ+10,并且如果Δ≤8或者Δ≥12,则χ(G2)≤Δ+9;

)如果m((2adG)<3,Δ≠5,则χ(G2)≤Δ+5;如果madG)<3,Δ=5,则χ(G2)≤11;

16[]6

(定理1 如果madG)<,则χ(G2)=Δ(G)+1.

7[]7

定理2 设图G的最大度Δ(G)=Δ,则有如下结论:

[](madG)<4,而χ(G2)=2Δ(G)+2,进而否定了Charentier猜想.此外,Charentier8还证明了对于pp

,如果m(充分大的Δ(G)adG)<4,则χ(G2)≤3Δ(G)+3.因此,有

{(}≤3()2Δ(G)axG2)madG)<4Δ(G)2+2≤m+3.χ(

14)如果m(3adG)<,则χ(G2)≤Δ+5.

5[]

(]通过构造图G,使得图G满足Charentier猜想8:如果madG)<4,则χ(G2)≤2Δ(G).文献[9p

[]

( 定理38 如果madG)<4并且Δ(G)≥8,则χ(G2)≤3Δ(G)+1.

[]

对于最大度Δ(的上界为3G)≤5的图,G2)Δ(G)+1,并且该上界是紧的8.χ(

…,,定义1 在图G中,若存在一个顶点的排序σ:vvv2≤i≤n)1,2,n,使得对任意的vi(

}≤r成立,则称图G是rvvvi-退化的,且排序σ是好排序.i~j本文主要结果如下:

(定理4 如果madG)<4且Δ(G)≥7,则χ(G2)≤3Δ(G)+1.(定理5 如果madG)≤4且Δ(G)≥8,则χ(G2)≤3Δ(G)+5.

2 定理4的证明

(证法,假设图G是满足madG)<4且Δ≥7边数最少的极小反例,G2不是3Δ-退化的.先令G中每个

(顶点的初始权重为w(v)=d(v)-4,由于madG)<4,因而初始总权重为负;然后利用权转移规则,将顶点间的权重进行相互转移,计算经过权重转移后的总权重,如果是非负的,则得矛盾.在每个顶点权重转移过程中,需找出在图G中所规避的构型.

2.1 相关命题

)定义2 设v是图G的d表示点v在图G中i·点,用dv)·邻域的个数(i=2,3.当d(v)≥4时,i(

对顶点定义如下:

)如果d(1v)-dv)≥7,则v是好顶点.2()如果d(2v)-dv)=6,则v是弱好顶点.2(

(要证明定理4,只需证明对任意的图G满足madG)<4且Δ≥7时,G2是3Δ-退化的即可.用反

dv)=1时,v称为B型第二类的.3(

)如果d(5v)-dv)=3,则v是坏顶点.2(

)如果d(3v)-dv)=5,则v是A型弱坏顶点.当dv)=0时,v称为A型第一类的;当2(3(1≤dv)≤3时,v称为A型第二类的.3(

)如果d(4v)-dv)=4,则v是B型弱坏顶点.当dv)=0时,v称为B型第一类的;当2(3((首先假设图G是极小反例,即图G满足madG)<4并且Δ≥7,但G2不是3Δ-退化的.根据图G22

的极小性,在图G中删除某条u是3是3v边后(G\\uv)Δ-退化的,最后只需证明GΔ-退化的,得矛盾.

命题1 图G中的每个4+-顶点都是定义2中的一种.

对于第一种情形,因为d(是v)≥4,所以v有2·邻域,记为w.根据图G的极小性,(G\\vw)

的好排序,可先从σ中删除v及v的23Δ-退化的.假设σ是(G\\vw)·邻域,形成新的排序σ′,然后在

σ′中将删除的点依次加回.对于点v,排在点v之前出现的邻域个数至多为2Δ+Δ-2=3Δ-2.对于每

点,则根据定义有d(v)-dv)≤2,或者d(v)-dv)=4并且dv)≥2,或者d(v)-dv)=5并且2(2(3(2(dv)≥4.3(

证明:假设G中的顶点v既不是坏顶点,也不是B型弱坏顶点、A型弱坏顶点、弱好顶点和好顶

个2·顶点,与之相邻且排在其之前的顶点个数至多为2Δ.因此G2是3Δ-退化的,矛盾.

),出现在其之前且与其相邻的顶点至多有()个.最后对于22Δ+Δ-4+4=3Δ.对于wi=1,22Δ+4·i(

顶点,与之相邻且出现在其之前的顶点个数至多为2Δ.因此G2是3Δ-退化的,矛盾.

的好排序,可做如下操作:先从σ中删除v,3Δ-退化的.假设σ是(G\\vw1)w1,w2,w3,w4及v的2·邻

域,形成新的排序σ′,然后在σ′中将删除的点依次加回.对于点v,排在点v之前且与其相邻的顶点个

对于第三种情形,令w1,是w2,w3,w4分别是v的3·邻域.根据图G的极小性,(G\\vw1)

的.假设σ是(的好排序,可做如下操作:先从σ中删除v,邻域,形成新的排G\\vw1)w1,w2及v的2·序σ′,然后在σ′中将删除的点依次加回.对于点v,排在点v之前且与其相邻的顶点个数至多为

对于第二种情形,令w1,是3w2分别是v的两个3·邻域.根据图G的极小性,(G\\vw1)Δ-退化

2Δ+5.最后对于2·顶点,与其相邻且出现在其之前的顶点至多有2Δ个.因此G2是3Δ-退化的,矛盾.证毕.

命题2 在图G中,3--点不与3--点相邻.

2证明:设u,是3v是图G中两个相邻的3--点.根据图G的极小性,(G\\uv)Δ-退化的.假设σ是

,与其相邻且出现在其之前的顶点个数至多为数至多为Δ+Δ-5+8=2Δ+3.对于wi=1,2,3,4)i(

(的好排序,可先从σ中删除u和v,形成新的排序σG\\uv)′,然后在σ′中将u和v依次加回.显然,与u相邻并且排在u前面的顶点个数至多为2Δ+3,v同理.因此G2是3Δ-退化的,矛盾.证毕.2

证明:设v是图G的坏顶点,是3u是与v相邻的3·顶点.根据图G的极小性,(G\\vu)Δ-退化

的.假设σ是(的好排序,可先从σ中删除v和u及v所有的2G\\vu)·邻域,形成新的排序σ′,然后在

命题3 在图G中,坏顶点不与3·点相邻,并且其4+邻域点不是坏顶点.

σ′中将删除的点依次加回来.首先对于点v,出现在点v之前且与其相邻的顶点个数至多为

)个.最后对于2顶点,排在其之前2Δ+Δ-3+2=3Δ-1.对于点u,排在其之前的邻域至多有(2Δ+3·假设x是图G的坏顶点,并且x是v的4+邻域点,w是v的2·邻域.根据图G的极小性,

(是3的好排序,可先从σ中删除v及v和x所有的2G\\vw)Δ-退化的.假设σ是(G\\vw)·邻域,形成新的排序σ′,然后在σ′中将删除的点依次加回.对于点v,排在点v之前且与其相邻的顶点个数至多为且与其相邻的顶点至多有2Δ个.因此G2是3Δ-退化的,矛盾.

个22Δ+Δ-3+3=3Δ.对于(2Δ-6)·邻域的每个点,与之相邻且排在其之前的顶点个数至多为Δ+4+2Δ-6=3Δ-2.因此G2是3Δ-退化的,矛盾.证毕.

22据图G的极小性,(是3的好排序,可先从σ中删除点v及v和wG\\vx)Δ-退化的.假设σ是(G\\vx)

命题4 如果v是图G中B型弱坏顶点u的坏邻域,则v至少有2个好邻域.

证明:假设w(是v的邻域,并且w不是好顶点.因为v是坏邻域,所以v有2w≠u)·邻域x.根

所有的2·邻域,形成新的排序σ′,然后在σ′中将删除的点依次加回.首先对于点v,与点v相邻并且排

Δ-3+4+Δ+d(w)w)Δ+1+d(w)w)≤2Δ+7-d=2-d2(2((因为w不是好顶点,所以d(w)-dw)≤6).此外,与2·顶点相邻且排在其之前的顶点至多有2(2Δ个.因此G2是3Δ-退化的,矛盾.证毕.

命题5 在图G中,每个B型第一类的弱坏顶点至多有2个坏邻域.

22性,(G\\uvΔ-退化的.假设σ是(G\\uvvvv1)是31)的好排序,可先从σ中删除u,1,2,3及其所有的

在之前的顶点个数至多为

证明:设u是B型第一类的弱坏顶点,假设u至少有3个坏邻域,记为vvv1,2,3.由图G的极小

,排在v2·邻域,形成新的排序σ′,然后在σ′中将删除的点依次加回.对于vi=1,2,3)i(i之前且与其相邻的顶点个数至多为2Δ+Δ-3+3=3Δ.对于点u,与之相邻且排在之前的顶点个数至多为Δ-4+Δ+3×3=2Δ+5.对于2·顶点,与之相邻且排在其之前的顶点至多有2Δ个.因此G2是3Δ-退化的,矛盾.证毕.

命题6 在图G中,没有好邻域但有坏邻域的B型第一类弱坏顶点至少有1个弱好邻域.

证明:设u是没有好邻域但有坏邻域的B型第一类弱坏顶点,且u没有弱好邻域,记其中的1个

坏邻域为v假设σ是(vvG\\uvΔ-退化的.G\\uv1,其他邻域为v2,3,4.由图G的极小性,(1)是31)的

在σ′中将删除的点依次加回.首先对于vΔ+Δ-3+3=1,排在其之前且与其相邻的顶点个数至多为23Δ.对于点u,与u相邻且排在其之前的顶点个数至多为

,好排序,可做如下操作:先从σ中删除u,vvvvv·邻域,形成新的排序σ′,然后1及u1,2,3,4所有的2

Δ-4+3+3×5=Δ+14())因为v既不是好邻域也不是弱好邻域,所以d(i=2,3,4v-dv≤5.最后对于2·顶点,与之i(i)2(i)相邻且排在其之前的顶点至多有2Δ个.因此G2是3Δ-退化的,矛盾.证毕.

命题7 每个B型第二类的弱坏顶点至多有1个坏邻域.

22邻域.由图G的极小性,(是3的好排序,可做如下操作:先从σG\\uw)Δ-退化的.假设σ是(G\\uw)

Δ-4+d(vvvvvvvv-d+d(-d+d(-d+d(-d≤1)2(1)2)2(2)3)2(3)4)2(4)

证明:设u是B型第二类的弱坏顶点,且u至少有2个坏邻域,记为v·1和v2,令w是u的3

中删除u和w及u,vv·邻域,形成新的排序σ′,然后在σ′中将删除的点依次加回.首先对1,2所有的2

于点u,与u相邻且排在其之前的顶点个数至多为Δ-4+Δ+2×3+2=2Δ+4.其次,对于3·顶点w,)与w相邻且排在其之前的顶点至多有(个.最后对于22Δ+4·顶点,与之相邻且排在其之前的顶点至1个好邻域的B型第二类弱坏顶点至少有1个弱好邻域.

证明:设u是图G中没有好邻域的B型第二类弱坏顶点,且u至多有1个弱好邻域.令w是u的中将删除的点依次加回.如果u有1个弱好邻域,记为v1,则与u相邻且排在u之前的顶点个数至多为

多有2Δ个.因此G2是3Δ-退化的,矛盾.证毕.

命题8 在图G中,没有好邻域的B型第二类弱坏顶点至少有2个弱好邻域;有坏邻域且仅有

)是3的好3·邻域,其他邻域为vi=1,2,3.由图G的极小性,(G\\uw)Δ-退化的.假设σ是(G\\uw)i(

排序,可做如下操作:先从σ中删除u和w及u,vvv·邻域,形成新的排序σ′,然后在σ′1,2,3所有的2

Δ-2+d(vvvvvv4-d+d(-d+d(-d≤Δ-2+6+2×5=Δ+11)2(1)2)2(2)3)2(3)();如果u没有弱好邻域,则因为v既不是好邻域也不是弱好邻域,所以d(i=2,3v-dv≤5)i(i)2(i)Δ-2+d(vvvvvv3-d+d(-d+d(-d≤Δ-2+5×3=Δ+11)2(1)2)2(2)3)2(3)())因为v既不是好邻域也不是弱好邻域,所以d(顶点w,与i=1,2,3v-dv≤5.此外,对于3·i(i)2(i)同理,设u′是图G中有坏邻域且仅有1个好邻域的B型第二类弱坏顶点,且u′不存在弱好邻域.令w其中v′′′′′′是u′的3·邻域,其他邻域为vvv′唯一的好邻域,v′的坏邻域.因为u′不1,2,3,1是u2是u2存在弱好邻域,所以v是3′G\\u′w′)Δ-退化的.3既不是好顶点也不是弱好顶点.由图G的极小性,(

假设σ是(的好排序,可做如下操作:先从σ中删除u′′G\\u′w′)′和w′及u′,vv·邻域,形成2,3所有的2

与u相邻且排在其之前的顶点个数至多为

个.对于2w相邻且排在其之前的顶点至多有(2Δ+4)·顶点,与之相邻且排在其之前的顶点至多有2Δ个.因此G2是3Δ-退化的,矛盾.

()因为v所以d(′′′v-dv≤5.对于3·顶点w′,与w′相邻且排在3既不是好顶点也不是弱好顶点,3)2(3)是3Δ-退化的,矛盾.证毕.

新的排序σ′,然后在σ′中将删除的点依次加回.对于点u′,与u′相邻且排在其之前的顶点个数至多为

′′′′Δ-2+Δ+d(vvvvΔ+1+5=2Δ+6-d+d(-d≤22)2(2)3)2(3)

)其之前的顶点至多有(个.对于22Δ+4·顶点,与之相邻且排在其之前的顶点至多有2Δ个.因此G2

命题9 在图G中,设A型第一类弱坏顶点为u,且其邻域为vi=1,2,3,4,5).令i(

a={vvb={vvi:i是有2个好邻域的坏顶点},i:i是至多有1个好邻域的坏顶点},则有以下几种情形:

)当a=0时,1b≤3;)当a=1时,2b≤2;)当a=2时,3b≤2;)当a=3时,4b≤1.

相邻.根据图G的极小性,(可先vi=1,2,3,4)G\\uvΔ-退化的.假设σ是(G\\uvi(1)是31)的好排序,

从σ中删除u,vvvv·邻域,形成新的排序σ′,然后在σ′中将删除的点依次加回.因1,2,3,4及其所有的2

)当a=0时,假设b≥4,令至多有1个好邻域的坏顶点分别为v证明:1vvv1,2,3,4,并且u与

Δ-3+4+Δ+d(zzΔ+1+6=2Δ+7≤3Δ-d≤2i)2(i)()因为zz-dz≤6.对于点u,与u相邻且排在其之前的顶点个数至多为i不是好顶点,所以d(i)2(i)Δ-5+Δ+4×3=2Δ+7.对于2·顶点,与之相邻且排在其之前的顶点至多有2Δ个.因此G2是

v·邻域.在σ′中,与vi相邻且排在其之前顶点的个数时需删除zi的2i相邻且排在其之前的顶点个数至多为

)为v是至多有1个好邻域的坏顶点,所以vi=1,2,3,4i(i存在不是好顶点的邻域,记为zi.在寻找与

)并且u与v相邻.根据图G的极小性,(vi=1,2,3,4G\\uvΔ-退化的.假设σ是(G\\uv4,i(2)是32)

的好排序,可先从σ中删除u,vvv·邻域,形成新的排序σ′,然后在σ′中将删除2,3,4及其与v1所有的2

3Δ-退化的,矛盾.

)当a=1时,假设b≥3,令有2个好邻域的坏顶点为v2v1,至多有1个好邻域的坏顶点为v2,3,)的点依次加回.因为v是至多有1个好邻域的坏顶点,与第一种情形类似.对于u,在σi=2,3,4′i(中,与u相邻且排在其之前的顶点个数至多为Δ-5+Δ+4×3=2顶点,与之相邻且排在Δ+7.对于2·其之前的顶点个数至多为2Δ.因此G2是3Δ-退化的,矛盾.

)当a=2时,假设b≥3,令有2个好邻域的坏顶点为v31和v2,至多有1个好邻域的坏顶点为

(相邻.根据图G的极小性,vvvi=1,2,3,4,5)G\\uvΔ-退化的.假设σ是3,4,5,并且u与vi(3)是3

(G\\uvvvvv·邻域,形成新的排序σ′,然后3)的好排序,可先从σ中删除u,3,4,5及其与v1,2所有的2邻且排在其之前的顶点个数至多为2Δ.因此G2是3Δ-退化的,矛盾.

)当a=3时,假设b=2,令有2个好邻域的坏顶点为v4vv1,2,3,至多有1个好邻域的坏顶点为

在σ是至多有一个好邻域的坏顶点,与第一种情形类似.′中将删除的点依次加回.因为vi=3,4,5)i(在σ′中,对于u,与u相邻且排在其之前的顶点个数至多为Δ-5+5×3=Δ+10.对于2·顶点,与之相

σ′中,对于u,与u相邻且排在其之前的顶点个数至多为Δ-5+5×3=Δ+10.对于2·顶点,与之相邻且排在其之前的顶点个数至多为2Δ.因此G2是3Δ-退化的,矛盾.证毕.du)=2时,u至多有一个坏邻域;当du)=3时,u没有坏邻域.3(3(

证明:当d且u的3u)=1时,假设u至少有3个坏邻域vvv·邻域为x.根据图G的极小3(1,2,3,2·邻域,形成新的排序σ′,然后在σ′中将删除的点依次加回.对于u,与u相邻且排在其之前的顶点个数至多为Δ-5+Δ+3×3+2=2Δ+6.对于3度顶点x,与之相邻且排在其之前的顶点至多有()个.对于22Δ+5·顶点,与之相邻且排在其之前的顶点个数至多为2Δ.因此G2是3Δ-退化的,矛盾.

22的极小性,(是3的好排序,可先从σ中删除u,G\\uw1)Δ-退化的.假设σ是(G\\uw1)w1,w2及u,v1,22性,(是3的好排序,可先从σ中删除u和x及u,G\\ux)Δ-退化的.假设σ是(G\\ux)vvv1,2,3所有的

相邻.根据图G的极小性,(vi=1,2,3,4,5)G\\uvΔ-退化的.假设σ是4和v5,并且u与vi(4)是3

(G\\uvvvvv·邻域,形成新的排序σ′,然后4)的好排序,可先从σ中删除u,4,5及其与v1,2,3所有的2

)在σ是至多有1个好邻域的坏顶点,与第一种情形类似.在′中将删除的点依次加回.因为vi=4,5i(

命题10 设u是图G中A型第二类的弱坏顶点,当du)=1时,u至多有2个坏邻域;当3(

当du)=2时,假设u至少有2个坏邻域vv·邻域分别为w1和w2.根据图G3(1,2,且u的2个3

邻域,形成新的排序σv·′,然后在σ′中将删除的点依次加回.对于u,与u相邻且排在其之前2所有的2

),与之相邻且排在其之前的顶点的顶点个数至多为Δ-5+Δ+2×3+2×2=2Δ+5.对于wi=1,2i(至多有(个.对于22Δ+5)·顶点,与之相邻且排在其之前的顶点个数至多为2Δ.因此G2是

3Δ-退化的,矛盾.当du)=3时,假设u存在坏邻域v1,令u的3·邻域分别为w1,w2,w3.根据图G的极小性,3(

(是3的好排序,可先从σ中删除u,G\\uw1)Δ-退化的.假设σ是(G\\uw1)w1,w2,w3及u和v1所有的2·邻域,形成新的排序σ′,然后在σ′中将删除的点依次加回.对于u,与u相邻且排在其之前的顶点

()个.最后对于22Δ+5·顶点,与之相邻且排在其之前的顶点个数至多为2Δ.因此G2是3Δ-退化的,矛盾.证毕.

2.2 权转移规则

(因为madG)<4,所以有

v∈V(G)

,与之相邻且排在其之前的顶点至多有个数至多为Δ-5+Δ+3+2×3=2Δ+4.对于wi=1,2,3)i(

令每个顶点的初始权重为w(v)=d(v)-4,易知图G的初始总权重是负的.下面制定一些权重转

移规则,使得顶点间经过权重转移后,图G中每个顶点的权重是非负的,进而图G的总权重是非负的,形成矛盾.

1权转移规则1:每个顶点给权重1到其每个2·邻域以及给权重到其每个3·邻域.3权转移规则2:每个好顶点给权重5到其坏邻域.

121个好邻域.

权转移规则3:每个不是B型弱坏顶点的4+-点给权重1到其每个坏邻域,并且该坏邻域至多有

)(·V(d(v)v)G)≤madG)G)-4V(G)<0.-4=∑d(-4V(∑(

v∈V(G)

()3

权转移规则4:每个不是好顶点的4+-点给权重1到其每个坏邻域,并且该坏邻域有2个好邻域.

6权转移规则5:每个好顶点给权重1到其B型弱坏邻域.

3下面计算经过权重转移后各顶点的最终权重.

权转移规则6:每个弱好顶点给权重1到其B型弱坏邻域.

2.2.1 3--点根据权转移规则1,G中的每个2·顶点会从其每个邻域接收1的权重,而且不会失去任何权重,因此其最终权重是w′(v)=2-4+2×1=0.

同理,对于每个3·顶点,根据命题2,3·顶点不与3--点相邻,所以每个3·顶点不会失去任何权

重,而且根据权转移规则1,其会从自身的每个邻域接收1的权重,因此其最终权重

32.2.2 坏顶点令v是图G的坏顶点,根据权转移规则1,v将权重给相邻的2·邻域后,v的剩余权重为-1.此外,注意到坏顶点不是好顶点和弱好顶点,根据命题3,v不与3·点相邻并且v没有坏邻域,因此v不会再失去任何权重.

5如果v刚好有3个好邻域,则根据权转移规则2,v的最终权重是w′(v)=-1+3×>0;如果v121是w′(v)=3-4+3×=0.

51有2个好邻域,则根据权转移规则2,4,v会接收来自好邻域以及其他邻域2×+=1的权重,因126

此v的最终权重是非负的;如果v至多有1个好邻域,则根据命题4,v的邻域中不含有B型弱坏顶

2.2.3 B型弱坏顶点令v是图G的B型弱坏顶点.

)如果v是B型第一类的,则根据权转移规则1,1v将权重给相邻的2·邻域后,v的剩余权重是0.如果v没有坏邻域,则v不会再失去任何权重,v的权重是非负的;如果v有坏邻域,则根据命题4和命题5,v至多有2个坏邻域,而且这2个坏邻域都至少有2个好邻域,由权转移规则4,v最多再失去11的权重此时,若有好邻域,则根据权转移规则,会接收来自好邻域1的权重,因此其=.v5v633最终权重是非负的.否则,v没有好邻域但v有坏邻域,根据命题6,v至少有一个弱好邻域,由权转1移规则6,v会接收来自弱好邻域的权重,因此其最终权重也是非负的.

)如果v是B型第二类的,则根据权转移规则1,2v将权重给相邻的2·邻域和3·邻域后,其剩余

1点,根据权转移规则3,v至少会接收来自不是B型弱坏顶点的4+邻域3×=1的权重,因此v的最

终权重仍是非负的.

2×

1权重是-1.如果v没有坏邻域,此时若v有好邻域,由权转移规则5,v接收来自好邻域的权重,

则v的最终权重是非负的;否则v没有好邻域,根据命题8,v至少有2个弱好邻域,再根据权转移规12则6,v会接收来自弱好邻域2×=的权重,因此v的最终权重也是非负的;如果v有坏邻域,则

根据命题4和命题7,v至多有1个坏邻域,而且这个坏邻域至少有2个好邻域,由权转移规则4,

12的权重,因此的最终权重是非负的否则,若有个好邻域且有坏邻域,则根据

=v.v1v331的权重此时,若至少有个好邻域,则根据权转移规则,接收来自好邻域

.v25v6v最多需给坏邻域2×

1命题8及权转移规则5,6,v至少有1个弱好邻域,因此v会分别接收来自好邻域的权重及弱好邻域31的权重,的最终权重是非负的;若没有好邻域,则根据命题,至少有个弱好邻域,由权转移

vv8v2

3规则6,其会接收来自弱好邻域2×1=2的权重,因此其最终权重仍是非负的.

2.2.4 A型弱坏顶点令v是图G的A型弱坏顶点.

,且vb={vvi:i~vi是至多有1个好邻域的坏顶点}.

)如果v是A型第一类的,则根据权转移规则1,1v将权重给相邻的2·邻域后,其剩余权重是1.令

,且va={vvi:i~vi是有2个好邻域的坏顶点},

1),当a=0时,根据命题9中1b≤3,由权转移规则3,v最多会失去3×=1的权重,此时v的最终

3115),权重是非负的;当a=1时,根据命题9中2b≤2,由权转移规则3,4,v最多会失去+2×=636),的权重,此时v的最终权重是非负的;当a=2时,根据命题9中3b≤2,由权转移规则3,4,v最多

,会失去2×1+2×1=1的权重,此时v的最终权重是非负的;当a=3时,根据命题9中4)b≤1,

63b≤1,根据权转移规则3,4,v最多会失去4×a=5时,根据权转移规则4,v最多会失去5×

115由权转移规则3,4,v最多会失去3×+=的权重,此时v的最终权重是非负的;当a=4时,

636

15的权重,此时的最终权重是非负的=v.66)如果v是A型第二类的,则当d2v)=1时,根据权转移规则1,v将权重给相邻的2·邻域和3·3(

11+=1的权重,此时v的最终权重是非负的;当63邻域后,其剩余权重是2.根据命题10,v至多有2个坏邻域,再由权转移规则3,4,v最多会失去

2×

2·邻域和3·邻域后,其剩余权重是

12的权重,因此其最终权重是非负的;当()时,根据权转移规则,将权重给相邻的

=d21v3v=331根据命题,至多有个坏邻域,再由权转移规则,,最.10v134v3多会失去1的权重,因此其最终权重是非负的;当dv)=3时,根据权转移规则1,v将权重给相邻3(

3的2·邻域和3·邻域后,其剩余权重是0.根据命题10,v没有坏邻域,不会再失去权重,因此v的最终权重为0.

综上可见,v的最终权重是非负的.

2.2.5 弱好顶点令v是图G的弱好顶点.根据权转移规则1,v将权重给相邻的2·邻域后,此时v的剩余权重为2.因为v不是好顶点,根据权转移规则1,3,4,6,所以v会将权重给3·邻域、坏邻域及1与之相邻的B型弱坏顶点.因为d(v)-dv)=6,所以v至多会失去6×=2的权重,因此v的最2(

3终权重是非负的.

是v的22.2.6 好顶点令v是图G的好顶点,且记dv)·邻域的个数.根据权转移规则1,2,3,5,2()因为v是好顶点,所以至多有(个邻域分别会接收来自v的至多5的权重,因此其最终d(v)-dv)2(

12权重为

5()7()))w′(v)≥d(v)v)dv-dv)dv-dv)-4-d-(=(-4>02(2(2(

1212

()因为d(v)-dv)≥7.2(重也是非负的,与初始总权重是负的矛盾.

通过上述对顶点间的权重转移,可得图G中每个顶点的最终权重为非负的,因此图G的最终总权

3 定理5的证明

3.1 相关命题

定理5的证明类似定理4,需找出在图G中规避的构型.

定义3 设v是图G的d表示点v在图G中i·点,用dv)·邻域的个数(i=2,3,4).当i(d(v)≥5时,对顶点定义如下:

)如果d(1v)-dv)≥8,则v是优顶点.2()如果d(4v)-dv)=5,则v是A型弱坏顶点.当dv)=0时,v称为A型第一类的;当2(3(1≤dv)≤2时,v称为A型第二类的.3(

)如果d(5v)-dv)=4,则v是B型弱坏顶点.当dv)=0时,v称为B型第一类的;当2(3(

(首先假设图G是极小反例,即图G满足madG)≤4且Δ≥8,但G2不是(3Δ+4)-退化的.根据)如果d(2v)-dv)≥7,则v是好顶点.2()如果d(3v)-dv)=6,则v是弱好顶点.2(

dv)=1时,v称为B型第二类的.3(

)如果d(6v)-dv)=3,则v是坏顶点.2(()3Δ+4-退化的,得到矛盾.

图G的极小性,在图G中删除某条u是(v边后(G\\uv)3Δ+4)-退化的,最后只需证明G2是

命题11 图G中的每个5+-顶点都是定义3中的一种.

顶点,则根据定义有d(v)-dv)≤2,或者d(v)-dv)=4并且dv)≥2,或者d(v)-dv)=5并2(2(3(2(且dv)≥3.3(

对于第一种情形,因为d(是v)≥5,所以v有2°邻域,记为w.根据图G的极小性,(G\\vw)

证明:假设图G中的顶点v既不是坏顶点,也不是A型弱坏顶点、B型弱坏顶点、弱好顶点和好

()的好排序,可先从σ中删除v及v的23Δ+4-退化的.假设σ是(G\\vw)·邻域,形成新的排序σ′,然后在σ′中将删除的点依次加回.对于点v,排在点v之前出现的邻域个数至多为2Δ+Δ-2=3Δ-2.

),排在其之前且与其相邻的顶点个数至多为22Δ+Δ-4+4=3Δ.对于wi=1,2Δ+4.对于2·顶点,i(

)与之相邻且出现在其之前的顶点至多有2Δ个.因此G2是(3Δ+4-退化的,矛盾.

对于第三种情形,令w1,是w2,w3分别是v的3·邻域.根据图G的极小性,(G\\vw1)

()的好排序,可先从σ中删除v,3Δ+4-退化的.假设σ是(G\\vw1)w1,w2,w3及v的2·邻域,形成新的排序σ′,然后在σ′中将删除的点依次加回.对于点v,出现在点v之前且与其相邻的顶点个数至多为

2()的好排序,可先从σ中删除v,3Δ+4-退化的.假设σ是(G\\vw1)w1,w2及v的2·邻域,形成新的排序σ′,然后在σ′中将删除的点依次加回.对于点v,排在点v之前且与其相邻的顶点个数至多为

)对于每个2·顶点,与之相邻且排在其之前的顶点个数至多为2Δ.因此G2是(3Δ+4-退化的,矛盾.

对于第二种情形,令w1,是w2分别是v的2个3·邻域.根据图G的极小性,(G\\vw1)

),出现在其之前的邻域个数至多为22Δ+Δ-5+6=3Δ+1.对于wi=1,2,3Δ+5.对于2·顶点,与i(

)之相邻且排在其之前的顶点至多有2Δ个.因此G2是(3Δ+4-退化的,矛盾.证毕.

证明:设u,是(v是图G中两个相邻的4--顶点.根据图G的极小性,(G\\uv)3Δ+4)-退化的.

假设σ是(的好排序,可先从σ中删除u和v,形成新的排序σG\\uv)′,然后在σ′中将u和v依次加回.

命题12 在图G中,4--点不与4--点相邻.

显然,对于点u,与u相邻并且排在其之前的顶点至多有(个,3Δ+4)v同理.因此G2是()3Δ+4-退化的,矛盾.证毕.

2(的好排序,可先从σ中删除v和u及v所有的2G\\vu)·邻域,形成新的排序σ′,然后在σ′中将删除的点依次加回.对于点v,出现在v之前且与其相邻的顶点个数至多为2Δ+Δ-3+2=3Δ-1.对于3·点

证明:设u是与v相邻的3是(·顶点.根据图G的极小性,(G\\vu)3Δ+4)-退化的.假设σ是

命题13 在图G中,坏顶点v既不与3·点相邻也不与4·点相邻,并且v的5+邻域点不是坏顶点.

)个.对于2顶点,排在其之前且与其相邻的点至多有2u,排在u之前的邻域至多有(2Δ+3·Δ个.因此

)G2是(3Δ+4-退化的,矛盾.

的好排序,可先从σ中删除v和w及v所有的2·邻域,形成新的排序σ′,然后在σ′中将删除的点依次

加回.对于点v,排在点v之前且与其相邻的顶点个数至多为2点w,排在wΔ+Δ-3+3=3Δ.对于4·之前的邻域至多有(个.对于23Δ+3)·顶点,排在其之前且与其相邻的点至多有2Δ个.因此G2是

)设w是与v相邻的4是(·顶点.根据图G的极小性,(G\\vw)3Δ+4-退化的.假设σ是(G\\vw)

()3Δ+4-退化的,矛盾.

假设x是图G中的坏顶点,并且x是v的5+邻域点,w是v的2·邻域.根据图G的极小性,

()是(的好排序,可先从σ中删除v及v和x所有的2邻域,G\\vw)3Δ+4-退化的.假设σ是(G\\vw)·形成新的排序σ′,然后在σ′中将删除的点依次加回.对于点v,排在点v之前且与其相邻的顶点个数至

)多为2个2Δ+Δ-3+3=3Δ.对于(2Δ-6·邻域的每个点,与之相邻且出现在其之前的顶点个数至多中B型弱坏顶点u′的坏邻域,则v′至少有2个优邻域.

证明:假设w(是v的邻域,并且w不是优顶点.因为v是坏邻域,所以v有2w≠u)·邻域x.根和w所有的2邻域,形成新的排序σ·′,然后在σ′中将删除的点依次加回.首先对于点v,与v相邻并且排在其之前的顶点个数至多为

)为Δ+4+2Δ-6=3Δ-2.因此G2是(3Δ+4-退化的,矛盾.证毕.

命题14 如果v是图G中A型弱坏顶点u的坏邻域,则v至少有2个优邻域.同理,若v′是图G22

)据图G的极小性,(是(的好排序,可先从σ中删除v及vG\\vx)3Δ+4-退化的.假设σ是(G\\vx)

Δ-3+5+Δ+d(w)w)≤2Δ+2+7=2Δ+9-d2(

()因为w不是优顶点,所以d(w)-dw)≤7.此外,与2·顶点相邻且排在其之前的顶点个数至多为2(

)2Δ.因此G2是(3Δ+4-退化的,矛盾.

同理可证v′至少有2个优邻域.证毕.

命题15 每个B型第一类的弱坏顶点至多有2个坏邻域.

是(B型第一类弱坏顶点,所以u有2·邻域x,由图G的极小性,(G\\ux)3Δ+4)-退化的.假设σ是

(的好排序,可先从σ中删除u及u,G\\ux)vvv·邻域,形成新的排序σ′,然后在σ′中将1,2,3所有的2

删除的点依次加回.对于点u,与之相邻且排在其之前的顶点个数至多为Δ-4+Δ+3×3=2Δ+5.对

证明:设u是B型第一类的弱坏顶点,且u至少有3个坏邻域,分别记为vvv1,2,3.因为u是

)于2·顶点,与之相邻且排在其之前的顶点至多有2Δ个.因此G2是(3Δ+4-退化的,矛盾.证毕.有1个弱好邻域的B型第一类弱坏顶点至多有1个坏邻域.

命题16 在图G中,没有好邻域的B型第一类弱坏顶点至少有1个弱好邻域;没有好邻域但至少证明:设u是没有好邻域的B型第一类弱坏顶点,且u没有弱好邻域,其邻域设为vvvv1,2,3,4.

2因为u是B型第一类弱坏顶点,所以u有2是(·邻域x,由图G的极小性,(G\\ux)3Δ+4)-退化的.2假设σ是(的好排序,可先从σ中删除u及u,G\\ux)vvvv·邻域,形成新的排序σ′,然1,2,3,4所有的2后在σ′中将删除的点依次加回.对于点u,与u相邻且排在其之前的顶点个数至多为

Δ-4+4×5=Δ+16())因为v既不是弱好邻域也不是好邻域,所以d(i=1,2,3,4v-dv≤5.对于2·顶点,与之相i(i)2(i)

)邻且排在其之前的点至多有2Δ个.因此G2是(3Δ+4-退化的,矛盾.v′是B型第一类弱坏顶点,所以u′有2·邻域x′,由2,其他邻域为z和w,其中z是弱好邻域.因为u22

图G的极小性,(是(的好排序,可先从σ中删除uG\\u′x′)3Δ+4)-退化的.假设σ是(G\\u′x′)′及

Δ-4+d(vvvvw)w)z)z)≤-d+d(-d+d(-d+d(-d1)2(1)2)2(2)2(2(

设没有好邻域但至少有1个弱好邻域的B型第一类弱坏顶点为u′,且其至少有2个坏邻域v1和

Δ-4+d(vvvvvvvv-d+d(-d+d(-d+d(-d≤1)2(1)2)2(2)3)2(3)4)2(4)

u′,w,vvz所有的2·邻域,形成新的排序σ′,然后在σ′中将删除的点依次加回.对于u′,与u′相邻1,2,

且排在其之前的顶点个数至多为

Δ-4+2×3+2×6=Δ+14

(因为w不是好邻域,所以d(w)-dw)≤6).对于2·顶点,与之相邻且排在其之前的顶点至多有2(

)2Δ个.因此G2是(3Δ+4-退化的,矛盾.证毕.

命题17 在图G中,每个B型第二类的弱坏顶点u至少有1个好邻域,此外u至多有1个坏邻域.

)是(的好排序,可先从σ中删除u和w及u,3Δ+4-退化的.假设σ是(G\\uw)vvv·邻1,2,3所有的2

域,形成新的排序σ′,然后在σ′中将删除的点依次加回.对于点u,与u相邻且排在其之前的顶点个数

证明:设u没有好邻域,令w是u的3·邻域,其他邻域为vvvG\\uw)1,2,3.由图G的极小性,(

Δ-4+2+d(vvvvvv6-d+d(-d+d(-d≤Δ-2+6×3=Δ+11)2(1)2)2(2)3)2(3)()因为v不是好顶点,所以d(i=1,2,3v-dv≤6).此外,对于3·顶点w,与w相邻且排在其i(i)2(i)()3Δ+4-退化的,矛盾.

)设u至少有2个坏邻域,记为v由图G的极小性,(是(G\\uw)3Δ+4-退化的.假设σ是1和v2.

(的好排序,可先从σ中删除u和w及u,G\\uw)vv·邻域,形成新的排序σ′,然后在σ′中1,2所有的2将删除的点依次加回.对于u,与u相邻且排在其之前的顶点个数至多为

)之前的顶点至多有(个.对于22Δ+4·顶点,与之相邻且排在其之前的顶点至多有2Δ个.因此G2是

至多为

Δ-4+2+d(vvvvΔ+4.-d+d(-d+Δ=21)2(1)2)2(2)对于3个.对于2·顶点w,与之相邻且排在其之前的顶点至多有(2Δ+4)·顶点,与之相邻且排在其之)前的顶点至多有2Δ个.因此G2是(3Δ+4-退化的,矛盾.证毕.

命题18 在图G中,有且仅有1个好邻域的B型第二类弱坏顶点至少有1个弱好邻域.

证明:设u是有且仅有1个好邻域的B型第二类弱坏顶点,且u没有弱好邻域,令w是u的3·邻

)域,其他邻域为v由图G的极小性,(是(vG\\uw)3Δ+4-退化的.假设σ是1为u的好邻域,2和v3.

(的好排序,可先从σ中删除u和w及u,G\\uw)vv·邻域,形成新的排序σ′,然后在σ′中2,3所有的2

Δ-4+2+Δ+d(vvvvΔ+8-d+d(-d≤Δ-2+Δ+2×5=22)2(2)3)2(3)

())因为v既不是好邻域又不是弱好邻域,所以d(顶点w,与wi=2,3v-dv≤5.此外,对于3·i(i)2(i))2Δ个.因此G2是(3Δ+4-退化的,矛盾.证毕.

命题19 在图G中,每个A型第一类的弱坏顶点至多有4个坏邻域.

相邻且排在其之前的顶点至多有(个.对于22Δ+4)·顶点,与之相邻且排在其之前的顶点至多有

将删除的点依次加回.对于点u,与u相邻且排在其之前的顶点个数至多为

vv·邻域,形成新的排序σ′,然后在σ′中将删除的点依次加回.对于vi=1,2,3,4,4,5及其所有的2i(),与之相邻且排在其之前的顶点个数至多为25Δ+Δ-3+4=3Δ+1.对于u,与u相邻且排在其之前)的顶点至多有(个.对于2Δ-5+5×3=Δ+10·顶点,与之相邻且排在其之前的顶点个数至多为2Δ.)因此G2是(3Δ+4-退化的,矛盾.证毕.

命题20 设u是图G中A型第二类的弱坏顶点,当du)=1时,u至多有2个坏邻域;当3(

)性,(是(的好排序,先从σ中删除u和x及u,G\\ux)3Δ+4-退化的.假设σ是(G\\ux)vvv1,2,3所

)的极小性,(G\\uv3Δ+4-退化的.假设σ是(G\\uvvvv1)是(1)的好排序,可先从σ中删除u,1,2,3,

证明:设u是图G中A型第一类的弱坏顶点,且u至少有5个坏邻域vvvvv1,2,3,4,5.根据图Gdu)=2时,u至多有1个坏邻域.3(

证明:当d记u的3u)=1时,假设u至少有3个坏邻域vvv·邻域为x.根据图G的极小3(1,2,3,有的2·邻域,形成新的排序σ′,然后在σ′中将删除的点依次加回.对于点u,与u相邻且排在其之前的())个.对于22Δ+5·顶点,与之相邻且排在其之前的顶点个数至多为2Δ.因此G2是(3Δ+4-退化的,矛盾.

当d记u的3u)=2时,假设u至少有2个坏邻域vv·邻域分别为w1和w2.根据图G的极3(1,2,

)小性,(是(的好排序,先从σ中删除u,G\\uw1)3Δ+4-退化的.假设σ是(G\\uw1)w1,w2及u,v1,)的顶点至多有(个.对于22Δ+5·顶点,与之相邻且排在其之前的顶点个数至多为2Δ.因此G2是

)若u的邻域中不存在B型弱坏顶点,则u至多有5个邻域或者是31·顶点或者是坏顶点;

)若u的邻域中存在1个B型弱坏顶点,则u至多有4个邻域或者是32·顶点或者是坏顶点;)若u的邻域中存在2个B型弱坏顶点,则u至多有3个邻域或者是33·顶点或者是坏顶点;)若u的邻域中存在3个B型弱坏顶点,则u至多有2个邻域或者是34·顶点或者是坏顶点;)若u的邻域中存在4个B型弱坏顶点,则u至多有1个邻域或者是35·顶点或者是坏顶点;)若u的邻域中存在5个B型弱坏顶点,则u的邻域中不存在36·顶点或者是坏顶点.)若弱好顶点u不存在B型弱坏邻域,则假设u至少有6个邻域v证明:分别1vvvvv1,2,3,4,5,6,顶点个数至多为Δ-5+Δ+3×3+2=2Δ+6.对于3·点x,与之相邻且排在其之前的顶点至多有

邻域,形成新的排序σv·′,然后在σ′中将删除的点依次加回.对于点u,与u相邻且排在其之2所有的2

,与之相邻且排在其之前前的顶点个数至多为Δ-5+Δ+2×3+2×2=2Δ+5.对于3·点wi(i=1,2)()3Δ+4-退化的,矛盾.证毕.

命题21 设u是图G的弱好顶点,除u的2·邻域外,u的其他邻域有以下几种情形:

邻域,形成新的排序σ假vv·′,然后在σ′中将删除的点依次加回.对于v5,6及其所有的2i中的坏顶点,设v是坏顶点,与vi=1,2,3,4,5,6)Δ+5+Δ-3=3Δ+2.i(i相邻且排在其之前的顶点个数至多为2)个.对于所有剩余的2顶点,与之相邻且排在其之3·点,与之相邻且排在其之前的顶点至多有(2Δ+6·)前的顶点个数至多为2Δ.因此G2是(3Δ+4-退化的,矛盾.对于点u,在σ′中,与u相邻且排在其之前的顶点个数至多为Δ-6+6×3=Δ+12.对于vi中剩余的

假设σ是(是G\\uvv·邻域w,根据图G的极小性,(G\\vw)1)的好排序;否则,1是坏顶点,其21

()的好排序.在这两种情形下,均可从σ中删除u,3Δ+4-退化的,故假设σ是(G\\vw)vvvv11,2,3,4,

2是3·顶点或者是坏顶点.如果v·顶点,则根据图G的极小性,(G\\uv3Δ+4)-退化的,故1是31)是(

)若弱好顶点u有1个B型弱坏邻域,则假设u至少有5个邻域是32·顶点或者是坏顶点,记为

)vvvvv·顶点,则根据图G的极小性,(G\\uv3Δ+4-退化的,故假设σ是1,2,3,4,5.如果v1是31)是(

22(是G\\uvv·邻域w,根据图G的极小性,(G\\vw)1)的好排序;否则,1是坏顶点,其有212()的好排序.在这两种情形下,均可从σ中删除u、3Δ+4-退化的,故假设σ是(G\\vw)3·顶点和坏1

顶点及其与B型弱坏顶点所有的2·邻域,形成新的排序σ′,然后在σ′中将删除的点依次加回.对于vi)中的坏顶点,同1.对于点u,在σ′中,与u相邻且排在其之前的顶点个数至多为Δ-6+1×4+)与之相邻且排在其之前的顶点个数至多为2Δ.因此G2是(3Δ+4-退化的,矛盾.

))),故略.的证明同23~6

)个.对于23×5=Δ+13.对于v·点,与之相邻且排在其之前的顶点至多有(2Δ+6·顶点,i中剩余的3

3.2 权转移规则

(因为madG)≤4,所以有

v∈V(G)

令每个顶点的初始权重为w(v)=d(v)-4,则易知图G的初始总权重是非正的.通过制定一些权重转

移规则,使得顶点间经过权重转移后,图G中每个顶点的权重为正,进而图G的最终总权重为正,构成矛盾.

对于图G中的点v,dv)和dv)分别表示点v的2·邻域和4·邻域的个数.令2(4(

)(·V(d(v)v)G)≤madG)G)-4V(G)≤0.-4=∑d(-4V(∑(

v∈V(G)

()4

1由{)},{)},当εD2=maxdvDaxdvεεε.D2和D4的定2(4=m4(1,2取足够小时,有D21+D42156156其每个4·邻域.

28权转移规则7:每个顶点给权重1+ε·邻域,给权重到其每个3·邻域及给权重ε1到其每个22到

75权转移规则8:每个优顶点给权重7到其坏邻域.

有1个优邻域.

8到其每个坏邻域,并且坏邻域至多权转移规则9:不是优顶点也不是弱坏顶点的5+-点给权重2

7521到其每个坏邻域,并且坏邻域有个优邻域权转移规则10:不是优顶点的5+-点给权重2.

10416权转移规则11:每个好顶点给权重到其每个B型弱坏邻域.

39下面计算经过权重转移后各顶点的最终权重.

5权转移规则12:每个弱好顶点给权重到其每个B型弱坏邻域.24

3.2.1 4--点根据权转移规则7,G中的每个2·顶点会从其每个邻域接收1+ε1的权重,而且不会失去任何权重,因此其最终权重是w′(v)=2-4+2×(1+ε=2ε0.1)1>

对于每个3·顶点,因为根据命题12,3·顶点不与4--点相邻,所以其不会失去任何权重,而且根

3顶点,因为根据命题1顶点不与4--点相邻,所以其不会失去任何权重,>0.同理,对于每个4·2,4·25

而且根据权转移规则7,其会从自身的每个邻域接收ε2的权重,因此其最终权重是w′(v)=4-4+4×ε4ε0.2=2>

8的权重,因此其最终权重是28据权转移规则7,其会从自身的每个邻域接收2w′(v)=3-4+3×=

7575

3.2.2 坏顶点令v是图G的坏顶点.根据权转移规则7,v将权重给相邻的2·邻域后,此时v的剩

余权重为-1-d根据命题1v)ε3,v不与3·顶点和4·2(1.此外,注意到坏顶点不是好顶点和弱好顶点,顶点相邻,并且v没有坏邻域,因此v不会再失去任何权重.

3×=-dv)ε0;如果v有2个优邻域,则根据权转移规则8,10,v会接收来自优邻域及其他2(1>

1616

如果v刚好有3个优邻域,则根据权转移规则8,v的最终权重是w′(v)=-1-dv)ε2(1+

114141邻域2×7+2=的权重,因此v的最终权重是w′(v)=-1-dv)ε=-dv)ε0;2(1+2(1>

16104131313

如果v至多有1个优邻域,则根据命题14,v的邻域中不含有弱坏顶点,根据权转移规则9,v至少会828接收来自不是弱坏顶点的5+邻域3×2=的权重,因此v的最终权重是w′(v)=-1-dv)ε2(1+

7525

3.2.3 B型弱坏顶点令v是图G的B型弱坏顶点.

)如果v是B型第一类的,则根据权转移规则7,1v将权重给相邻的2·邻域和4·邻域后,v的剩余权重是-dv)εdv)ε4和命题15,v至多有2个坏邻域,且每个坏邻域至2(1-4(2.此外,根据命题12121少有2个优邻域,由权转移规则10,v至多会失去2×=的权重.如果v有好邻域,则根据权转

1045216移规则11,v至少会接收来自好邻域的权重,因此v的最终权重是

21161;w′(v)≥-dv)εv)εv)εv)ε+=-d2(1-d4(2-2(1-d4(2>0

5239156

如果v没有好邻域,则根据命题16,v至少有1个弱好邻域,而且在这种情形下,v至多有1个坏邻21的权重根据权转移规则,至少会接收来自弱好邻域,因此根据权转移规则10,v最多会失去.12v104域5的权重,因此其最终权重是

2151

w′(v)≥-dv)εv)εv)εv)ε.+=-d2(1-d4(2-2(1-d4(2>0

10424156

)如果v是B型第二类的,则根据权转移规则7, 2v将权重给相邻的2·邻域、3·邻域和4·邻域后,28根据命题其剩余权重是-dv)εdv)ε.14和命题17,v至多有1个坏邻域,而且坏邻域至2(1-4(2-7521的权重如果至少有个好邻域,则由权转移少有2个优邻域,由权转移规则10,v至多会失去.v2

1041632规则11,v至少会接收来自其好邻域2×=的权重,因此v的最终权重是

3939

2821321913;w′(v)≥-dv)εv)εv)εv)ε-+=-d2(1-d4(2-2(1-d4(2>075104397800

如果v至多有1个好邻域,则根据命题17,v有且仅有1个好邻域,再根据命题18,v至少有1个弱好165邻域,由权转移规则11,12,v会接收来自好邻域的权重及至少接收来自弱好邻域的权重,因此其

3924

最终权重是

2821165169

w′(v)≥-dv)εv)εv)εv)ε.-++=-d2(1-d4(2-2(1-d4(2>0

7510439243900

3.2.4 A型弱坏顶点令v是图G的A型弱坏顶点.

)如果v是A型第一类的,则根据权转移规则7,1v将权重给相邻的2·邻域和4·邻域后,其剩余权重是1-d根据命题1v)εdv)ε4和命题19,v至多有4个坏邻域,而且坏邻域至少有2个优2(1-4(2.2121邻域,由权转移规则10,v最多会失去4×=的权重,因此其最终权重是

10426

215

w′(v)≥1-dv)εv)εv)εv)ε.=-d2(1-d4(2-2(1-d4(2>0

2626

283=-dv)ε0.2(1>2525

综上所述,v的最终权重为正.

)如果v是A型第二类的,则当d,邻域、邻域 2v)=1时,根据权转移规则7v将权重给相邻的2·3·3(47,和4根据命题1·邻域后,其剩余权重是-dv)εdv)ε4和命题20v至多有2个坏邻域,而且坏2(1-4(2.

752121,邻域至少有2个优邻域,再由权转移规则10v至多会失去2×=的权重,故其最终权重是

104524721869

v)εv)εv)εv)ε.-d=-d2(1-d4(2-2(1-d4(2>0

75523900

当dv)=2时,根据权转移规则7,v将权重给相邻的2·邻域、3·邻域和4·邻域后,其剩余权重是3(

w′(v)≥

19根据命题1-dv)εdv)ε4和命题20,v至多有1个坏邻域,而且坏邻域至少有2个优邻域,2(1-4(2.75

1921401

w′(v)≥v)εv)εv)εv)ε.-d=-d2(1-d4(2-2(1-d4(2>0

751047800

3.2.5 弱好顶点令v是图G的弱好顶点.根据权转移规则7,v将权重给相邻的2·邻域和4·邻域后,此时v的剩余权重是2-d因为v不是好顶点,所以根据权转移规则7,v)εdv)ε9,10,12,2(1-4(2.2828

×5=的权重,因此v的最终权重是7515

21的权重,故其最终权重是再由权转移规则10,v至多会失去

104

v会将权重给3·邻域、坏邻域及给与之相邻的B型弱坏顶点.若v的邻域中不存在B型弱坏顶点,则

),根据命题21中1v至多有5个邻域是3·顶点或者是坏顶点.根据权转移规则7,9,10,v最多会失去282;w′(v)≥2-dv)εv)εv)εv)ε=-d2(1-d4(2-2(1-d4(2>0

1515

),若v的邻域中存在1个B型弱坏顶点,则根据命题21中2v至多有4个邻域是3·顶点或者是坏顶5281021的权重,因此的最终权重是点,根据权转移规则7,9,10,12,v最多会失去1×+4×=v24756001021179;w′(v)≥2-dv)εv)εv)εv)ε=-d2(1-d4(2-2(1-d4(2>0600600

),若v的邻域中存在2个B型弱坏顶点,则根据命题21中3v至多有3个邻域是3·顶点或者是坏顶528461的权重,因此的最终权重是点,根据权转移规则7,9,10,12,v最多会失去2×+3×=v2475300461139;w′(v)≥2-dv)εv)εv)εv)ε=-d2(1-d4(2-2(1-d4(2>0300300

),若v的邻域中存在3个B型弱坏顶点,则根据命题21中4v至多有2个邻域是3·顶点或者是坏顶528823的权重,因此的最终权重是点,根据权转移规则7,9,10,12,v最多会失去3×+2×=v2475600823377;w′(v)≥2-dv)εv)εv)εv)ε=-d2(1-d4(2-2(1-d4(2>0600600

),则v至多有1个邻域是3若v的邻域中存在4个B型弱坏顶点,则根据命题21中5·顶点或者坏顶528181的权重,因此的最终权重是点,根据权转移规则7,9,10,12,v最多会失去4×+1×=v2475150181119;w′(v)≥2-dv)εv)εv)εv)ε=-d2(1-d4(2-2(1-d4(2>0150150

),若v的邻域中存在5个B型弱坏顶点,则根据命题2邻域或者是坏邻域,根据权转1中6v不存在3·525移规则12,v会失去5×=的权重,因此v的最终权重是

2424

2523;w′(v)v)εv)εv)εv)ε=2-d=-d2(1-d4(2-2(1-d4(2>0

2424

55,若v刚好有6个B型弱坏邻域,则根据权转移规则12v失去6×=的权重,因此v的最终权重是

是v的23.2.6 好顶点令v是图G的好顶点,并且记dv)·邻域个数.如果v不是优顶点,则对于2(

53w′(v)v)εv)εv)εv)ε.=2-d=-d2(1-d4(2-2(1-d4(2>0

44 综上所述,v的最终权重为正.

16)除去2个邻域,根据权转移规则7,·邻域外的其他(d(v)-dv)9,10,11,v会分别给每个邻域至多2(

的权重,因此其最终权重是

16(()23()))w′(v)≥d(v)v)v)εv)dv-dv)v)ε-4-d-d×dv-d=(-4-d2(2(1-2(2(2(1>03939

())因为d(个邻域分别v)-dv)≥7.如果v是优顶点,则根据权转移规则7,8,至多有(d(v)-dv)2(2(会接收来自v的最多7的权重,因此v的最终权重是

7(())w′(v)≥d(v)v)v)εdv-dv)-4-d-d=2(2(1-2(

9(())dv-dv)v)ε-4-d2(2(1>0

()因为d(v)-dv)≥8.2(

通过上述对顶点间的权重转移,得到图G中每个顶点的最终权重为正,因此图G的最终总权重也

为正,与初始总权重非正矛盾.

衷心感谢天津大学应用数学中心彭兴老师的鼓励和指导.

参

考

文

献

[:M,1] BONDYJA,MURTYUSR.GrahTheorithAlications[M].Londonacmillan1976:117-121.pywpp

(,():SerA)1969,268746-48.

[]2] KRAMERF,KRAMERH.UnProblèmedeColorationdesSommetsd’unGrahe[J.CRAcadSciParisp[],(/):3] KRAMERF,KRAMERH.ASurventheDistanceColorinfGrahs[J.DiscreteMath2008,30823yogop-[:U4] WEGNERG.GrahswithGivenDiameterandaColorinroblem[R].DortmundniversitfpgPyo[],:5] LIHKW,WANGWF.ColorinheSuareofanOuterlanarGrah[J.TaiwaneseJMath2006,10(4)gtqpp[6] HOSSEINIDOLAMAM,SOPENAE.OntheMaximumAveraeDereeandtheIncidenceChromaticNumbergg[]7] CHARPENTIERC,MONTASSIERM,RASPAUDA.L(-LabelinfSarseGrahs[J.JCombOtim,gopppp,q)[,]8] HOCQUARDH,KIMSJPIERRONT.ColorinuaresofGrahswithMadConstraints[J.DiscreteAlgSqppp[,]9] KIMSJPARKB.ColorintheSuareofGrahsWhoseMaximumAveraeDereeIsLessThan4[J.Discretegqpgg

,():Math2016,33941251-1260.,Math2019,271:64-73.():2013,254646-660.

],():ofaGrah[J.DiscreteMathTheorComutSci2005,71203-216.pp1015-1023.,Dortmund1977.422-426.

(责任编辑:赵立芹)

因篇幅问题不能全部显示，请点此查看更多更全内容

查看全文

全部栏目

稀疏图平方图的染色数上界