1. 引言
本文考虑的图都是简单无向图。对于一个平面图G,把它顶点集、边集、面集、最大度分别记为
,
,
和
,用
、
分别表示顶点、面的度,如果顶点v的度等于k (至少是k或至多是k),则称v是k-点(k+-点或k−-点)。1-点又称悬挂点,kl-点是指与l个2-点相邻的k-点,顶点v的一个k-邻点指的是
中度为k的顶点。k-圈指的是长为k的圈,如果两个圈至少有一个公共顶点(或一条公共边),则称它们是相交(或相邻的)。好3-面指的是不关联2-点的3-面,坏3-面指的是关联一个2-点的3-面。好4-面指的是不关联2-点的4-面,弱4-面是关联一个2-点的4-面,把一个关联两个不相邻2-点的4-面称为坏4-面。
表示与边uv的距离不超过2的边构成的集合,给定图G的一个边染色c,记
。
图G的强边染色(也称为2-距离边染色),是指对图G的边进行正常染色,使得长为3的路上的任意两条边染不同的颜色。强边染色所用颜色的最小整数称为图G的强边色数,记为
。1985年Erdős [1] 等提出了强边染色猜想:
猜想1 (Erdős, Nešet ř il)。设图G的最大度为Δ,则
1) 若Δ为偶数,则
;
2) 若Δ为奇数,则
。
当时,猜想显然成立。Andersen [2] 和Horák [3] 证明了当
时猜想成立。当
时,Cranston [4] 等证明了
。Molloy和Reed [5] 证明了当Δ充分大时,强边染色的上界不超过
。对于平面图强边染色的研究,始于Faudree [6] 等用四色定理和Vizing’(s)定理证明了平面图的强边色数
。当围长足够大时,文献 [7] [8] 证明了平面图的强边色数可以达到下界
。2014年,Hudák [9] 等证明了
的平面图G有
,后来Bensmail [10] 等把该结果改进为当平面图
时,
;当
且
时,
。孟献青在文献 [11] 证明了没有k-圈(
)且3-圈不相交的平面图有
,本文推广了该结果,证明了没有k-圈(
)且3-圈、4-圈互不相交的平面图其强边色数
。
2. 定理及其证明
定理1设最大度为
的平面图G不包含k-圈(
)且3-圈、4-圈互不相交,则G的强边色数
。
证明:当
时,由文献 [2] [3] ,定理成立。下面只需证明
的情形。假设定理1结论不成立,则存在一个不包含k-圈(
)且3-圈、4-圈互不相交,但
,使
最小的平面图,由极小性知,G为连通平面图,而对G的任何一个真子图
是
-强边可染的,同时G还具有以下性质。
2.1. 极小反例的性质
引理1 [10] 设v是图G的一个顶点且
。
1) 若
,则1-点的邻点是5+-点;
2) 若
,则2-点的两个邻点不能同时是两个3--点,或一个3−-点和一个43-点,或一个3−-点和一个43-点,或一个42-点和一个43-点;
3) 若
,则v至多与
个2−-点相邻;
4) 若
,则v至多与
个1-点相邻;若v恰好与
个1-点相邻。则v不与其他的2−-点相邻;
5) 若
,且v相邻
个1-点和
个2-点,则
,且至多有
个2-点的邻点是3−-点或43-点;
6) 若
,且v相邻
个2−-点,则这
个2−-点都是2-点,且这些2-点的另一个邻点是不同于43-点的4+-点。
引理2 [11] 若2-点v与3-圈关联,则v的另两个邻点是5+-点。
引理3 [11] 设G有一个3-圈
,满足
,
,
,则
1) v至多与
个2−-点相邻;
2) 若v与
个1-点相邻,则v至多只有一个2-邻点;
3) 若v与
个1-点和
个2-点相邻,则
,且至多有
个2-点的邻点是3−-点或43-点。
引理4 [12] 4-面不能关联两个相邻的2-点。
引理5 [12] 设v与弱4-面f关联,且f边界上的顶点按顺时针方向记为u,w,z,v,满足
,
,
。若v与
个1-点和
个2-点相邻,则
1)
,且若
,则
。
2) 若
,则
,且至多有
个2-点的邻点是3−-点或43-点。
引理6 [12] 设v与坏4-面f关联,且f边界上的顶点按顺时针方向记为u,w,z,v,满足
,
,
。若v与
个1-点和
个2-点相邻,则
1),且
;若
,则
。
2) 若
,
,则
,且至多有
个2-点的邻点是3−-点或43-点。
2.2. 权转移规则
对连通平面图G,由欧拉公式,有
及
,
可得:
对每一个
,定义其初始权值为
。对任意
,定义
,而对于
,
,则
。下面定义权转移规则,重新分配顶点和面的权,使得对每个
,都有
。由于只在顶点和面之间进行权转移,故权总和不变,从而
,矛盾。说明极小反例不存在,从而定理成立。
权转移规则如下:
R1 设v为1-点,则
R1.1 每个与v相关联的面f给v转2;
R1.2 每个与v相邻的5+-点给v转2;
R2 设v为2-点,
,且
,则
R2.1 若u是3−-点,则w给v转2;
R2.2 若u是43-点,则u给v转
,w给v转
;
R2.3 否则,u和w分别给v转1。
R3 若f为3-面,则
R3.1 每个与f相邻的面g给f转权1;
R3.2 每个5+-点给相关联的坏3-面转
。
R4 若f是4-面,面g与f有k条公共边,则g给f转权
。
下面验证新权
:
由R1.1知,每个面给相关联的1-点转2,而每增加一个悬挂点,面的度增加2,故悬挂点不影响面的转权。所以在验证面的权时,不考虑面f上的悬挂点。
首先检验。
设f为3-面,
。若f是好3-面,由R3.1,
;若f是坏3-面,由引理2,f关联两个5+-点,由R3.2,这两个5+-点给f转权
;再由R3.1,与f相邻的面给f转权
,因此
。
设f为4-面,
。当f为好4-面,由R4,
。
设f为k-面(
),则
。由于3-圈、4-圈之间互不相交,再由引理4,与4-面关联的2个2-点不相邻,故f至多与
个3-面、4-面关联,由R3,R4易知
。
下面再验证
。
情况1:v为1-点,则
。由引理1(1)知,1-点的邻点是5+-点,故由R1,
。
情况2:v为2-点,则
。由R2,
情况3:v为3-点,根据转权规则,3-点权值没有改变,所以
。
情况4:v为4-点,则
。由引理1(1),引理1(3),v无1-邻点且至多有3个2-邻点。
若v是40-点或41-点,由R2,
;
若v是42-点,设v的2个2-邻点是x,y,由引理1(2)可知x和y除v点外的邻点是不同于43-点的4+-点,故由R2.3,
;
若v是43-点,设v的3个2-邻点是x,y,z,由引理1(2)可知x,y和z除v点外的邻点是41-点或
5+-点,故由R2.2,
。
情况5:v为k-点(
),则
。分两种情况讨论:
1) v不与坏3-面关联。
由引理1(3),v至多与
个2--点相邻。
① 若v恰与
个2--点相邻,由引理1(6),v的
个2−-点都是2-点,且2-点的邻点是不同于43-点的4+-点,由R2.3,
。
② 若v恰与
个2−-点邻,设有
个1-邻点,由引理1(5),引理5(2),引理6(2)知,v的
个2-邻点中至多有
个2-点与3−-点或43-点相邻,即v至少有2个2-邻点除v点外的另一个邻点不是3−-点、43-点,此时由R1.2,R2.1,R2.3,有
。
③ 若v至多与
个2−-点相邻,设有
个1-邻点,
个2-邻点,则由引理1(4),引理5(1),引理6(1)知,仅当
,
;或
,
;或,
且v的2-邻点除v外的另一个邻点是3−-点时,顶点v转出的权最大,由R1.2,R2.1,
。
2) v与坏3-面
关联
。
由引理2,v与w均为5+-点。由引理3(1),v至多与
个2−-点相邻。
① 若v至多与
个2−-点相邻。由R2.3,v给u转权1,再由R1.2,R3.2知
。
② 若v恰与
个2−-点相邻,且v有
个1-邻点,由引理3(3),
且v的
个2-邻点中至多有
个2-点与3−-点或43-点相邻,根据R1.2,
R2,R3.2知,
。
综合以上各种情况,我们验证了对任意的
,都有
,从而得到如下矛盾的式子:
.
上面的这个矛盾说明G不存在,从而完成了定理1的证明。