不含特殊短圈平面图的无圈边染色*

郑丽娜

(浙江师范大学数理与信息工程学院，浙江金华 321004)

0 引言

本文仅考虑有限简单图．给定一个图G，用V(G)，E(G)，Δ(G)，δ(G)分别表示它的顶点集、边集、最大度、最小度．若uv∈E(G)，则称点u为点v的邻点，并用N(v)表示点v的邻点集合．点 v的度d(v)=|N(v)|;k-点(k+-点，k--点)表示度是k(至少为k，至多为k)的顶点．若能将图G画在平面上，使得它的边仅在端点处相交，则称G是可平面图．图的这种平面图上的画法称为图的平面嵌入，或称为平面图．

图G的正常k-边染色是指映射c：E(G)→{1，2，…，k}使得相邻的边染不同的颜色;若G有一个k-边染色，则称图G是k-边可染的;无圈k-边染色是指图G的一个正常的k-边染色，使其不产生双色圈;无圈边色数a'(G)是指使得图G有一个无圈k-边染色的最小整数k．

无圈边染色的概念最早是由 Fiamcˇík［1］提出的．Alon 等［2］证明了：对任何图 G 有 a'(G)≤64Δ(G);Molloy和 Reed［3］将这个界改进到 a'(G)≤16Δ(G);2005 年，Muthu等［4］证明了当 g(G)≥220 时，a'(G)≤4．52Δ(G)．2001 年，Alon 等［5］提出了如下著名的无圈边染色猜想：

猜想1 对任意图G，有a'(G)≤Δ(G)+2．

猜想1至今还未得到证实，仅知道一些特殊图类满足猜想1．Alon等［6］证明了确定任意图G的无圈边色数是一个NP-问题．Cohen等［7］还提出了如下猜想：

猜想2 设G是一个平面图，则存在一个整数Δ0，使得当Δ(G)≥Δ0时，就有a'(G)=Δ(G)．

对于不含特殊短圈的平面图，文献［8］证明了：若G不含4到8-圈，则a'(G)≤Δ(G)+2;文献［9］证明了：若G不含4-圈，5-圈或G不含4-圈，6-圈，则a'(G)≤Δ(G)+2;文献［10］证明了：若G不含4到11-圈且Δ(G)≥10或G不含4到9-圈且Δ(G)≥11，则a'(G)≤Δ(G)+1．

本文主要研究了不含特殊短圈平面图的无圈边染色问题，得到了以下结果：

定理1 设G是一个平面图，如果G不含4到8-圈，那么a'(G)≤Δ(G)+1．

1 结构引理

本节讨论的全部是平面图，且假设它们已经嵌入到平面上．设图G是平面图，通常用F(G)表示面集;对于f∈F，用d(f)表示面 f的度数;若一个k-面沿着某个方向的点依次为u1，u2，…，uk，则称这个面为(d(u1)，d(u2)，…，d(uk))-面;k-面(k+-面，k--面)表示度是 k(至少为 k，至多为 k)的面;(i，j，k+)-面表示i-点，j-点和 k+-点相连的3-面，其中i≤j≤k;对G的一个边染色c和顶点v∈V(G)，设 C(v)={c(uv)|u∈N(v)}．

设图G是满足定理1条件的一个边数极小反例，那么G是2-连通的．否则，设v是G的一个割点，G1，G2，…，Gt(t≥2)是 Gv的连通分支．由 G 的极小性知，对任意1≤i≤t，G'i=Gi∪{v}都有无圈 k-边染色ci．若点v相关联的边出现相同颜色，则通过每个ci进行色置换，使得点v相关联的边染不同色，从而可得G的一个无圈k-边染色，与G的极小性矛盾．

设 k=Δ(G)+1，为方便讨论，令颜色集 C={1，2，…，k}．此外，简记 Δ =Δ(G)．

首先给出一些定理1证明中需要用到的引理．

引理1 若d(v)=2，则v不与3--点相邻．

证明 假设v与一个3--点u相邻．设w≠u是v的另一邻点，G'=G-uv．由G的极小性知，G'有无圈 k-边染色 c，染色集 C={1，2，…，k}，不妨设 c(vw)=1．

1)若1∉C(u)，则用a0∈C(C(u)∪{1})染 uv．因|C(C(u)∪{1})|≥k-3≥1，故这样的颜色a0存在，且染色c仍是无圈的．

2)1∈C(u)．若存在 a1∈C(C(u)∪C(w))，则用 a1染 uv．否则，设 d(u)=3，u1≠v，u2≠v是 u 的另外 2 个邻点，c(uu1)=1，c(uu2)=2，A1=C{1，2}．若存在 b0∈A1，使得 G'中不含(1，b0)(u1，w)-双色路，则用 b0染 uv．否则，假设对于任意 i∈A1，G'中均有(1，i)(u1，w)-双色路，则 A1⊆C(w)∩C(u1)．又因d(w)≤Δ，d(u1)≤Δ，故C(w)=C(u1)=C{2}，因此可用2改染vw．与前面讨论类似，可设对于任意i∈A1，G'中均有(2，i)(u2，w)-双色路且 C(u2)=C{1}．此时交换 uu1和 uu2所染的色，再用 3 染 uv，从而可得G的一个无圈 k-边染色，与G的极小性矛盾．所以，v不与3--点相邻．引理1证毕．

引理2 若d(v)=d≥4，则v至多与d-2个2-点相邻．

证明 假设存在一个 d-点v与d-1 个2-点相邻．设N(v)={u1，u2，…，ud}，d(ui)=2，N(ui)={v，wi}，i=1，2，…，d-1，G'=G-u1v．由 G 的极小性知，G'有无圈 k-边染色 c，染色集 C={1，2，…，k}，不妨设 c(uiv)=i，i=2，3，…，d．

1)若 c(u1w1)∉{2，3，…，d}，则用 a2∈C({2，3，…，d}∪{c(u1w1)})染 u1v．因|C({2，3，…，d}∪{c(u1w1)})|≥k-d≥1，故这样的颜色a2存在，且染色c仍是无圈的．

2)若 c(u1w1)∈{2，3，…，d-1}，不妨设 c(u1w1)=2，则用 a3∈C({2，3，…，d}∪{c(u2w2)})染u1v．因|C({2，3，…，d}∪{c(u2w2)})|≥k-d≥1，故这样的颜色 a3存在，且染色 c仍是无圈的．

3)c(u1w1)=d．若存在 a4∈{1，d+1，d+2，…，k}C(w1)，则用 a4染 u1v．否则，{1，d+1，d+2，…，k}⊆C(w1)．又因为 d(w1)≤Δ 且 d∈C(w1)，所以至少存在1个颜色 j∈{2，3，…，d-1}C(w1)．此时，用 j改染u1w1，用a5∈C({2，3，…，d}∪{c(ujwj)})染u1v，可得G 的一个无圈k-边染色，与G 的极小性矛盾．所以，v至多与d-2个2-点相邻．引理2证毕．

引理3 在3-面的边界上没有2-点与4-点相邻．

证明 假设一个2-点u与一个4-点v相邻在一个3-面uvw的边界上，G'=G-uv．由G的极小性知，G'有无圈 k-边染色 c，染色集 C={1，2，…，k}，不妨设 c(uw)=1，c(vw)=2．

1)若1∉C(v)，则用 a6∈C(C(v)∪{1})染 uv．因|C(C(v)∪{1})|≥k-4≥1，故这样的颜色 a6存在，且染色c仍是无圈的．

2)1∈C(v)．设 v1，v3是 v的另外2 个邻点，c(vv1)=1，c(vv3)=3，A3=C{1，2，3}．若存在 b1∈A3，使得 G'中不含(1，b1)(v1，w)-双色路，则用 b1染 uv．否则，假设对于任意 j∈A3，G'中均有(1，j)(v1，w)-双色路，则 A3⊆C(w)∩C(v1)．又因 d(w)≤Δ，故 C(w)=C{3}．进一步，可假设对于任意 j∈A3，G'中均有(3，j)(v3，w)-双色路，则 A3⊆C(w)∩C(v3)．

只需考虑 d(v1)=d(v3)=Δ．显然有|{1，2，3}∩C(vi)|=2，i=1，3．此时，先抹去 uw 的色．

①若2∈C(v1)∩C(v3)，则交换vv1与 vv3所染的色，用3染uw，再用4染uv．

②若2∉C(vi)，i∈{1，3}，即 3∈c(vv1)，1∈c(vv3)，则 C(v1)=C(v3)=C{2}．若 w 到 v1无(2，4)-双色路，则分别用 2，1 改染 vv1，vw，用3 染 uw，再用4 染uv．若 w 到v1有(2，4)-双色路，则分别用2，1改染vv3，vw，用3染uw，再用4染uv．由双色路的唯一性知，w到v3无(2，4)-双色路．

③若2∈C(v1)，且2∉C(v3)，则分别用 3，2，1 改染 vv1，vv3，vw，用3 染 uw，再用 4 染 uv．

综上，可得G的一个无圈k-边染色，与G的极小性矛盾．所以，在3-面的边界上没有2-点与4-点相邻．引理3证毕．

引理4 若d(v)=4且v相邻2个2-点，则v不会关联3-面．

证明 假设v关联一个3-面uvw．设x，y是与 v相邻的2个2-点，x1，y1分别是2-点 x，y的另一邻点，G'=G-vx．由 G 极小性知，G'有无圈 k-边染色 c，染色集 C={1，2，…，k}．

1)若 c(xx1)∉C(v)，则用 a7∈C(C(v)∪{c(xx1)})染 vx．因|C(C(v)∪{c(xx1)})|≥k-4≥1，故这样的颜色a7存在，且染色c仍是无圈的．

2)c(xx1)∈C(v)，不妨设 c(vy)=1，c(vw)=2，c(uv)=3，A4=C{1，2，3}．考虑到 u，w 的对称性，故只需考虑以下2种情形：

①若 c(xx1)=1，则用 a8∈C(C(v)∪{c(yy1)})染 vx．因|C(C(v)∪{c(yy1)})|≥k-4≥1，故这样的颜色a8存在，且染色c仍是无圈的．

②c(xx1)=2．若存在a9∈C(C(v)∪C(w))，则用a9染vx．否则，可断言对于A4中的任一个颜色i都有x1到w的(2，i)-双色路，故A4⊆C(w)∩C(x1)．进一步，若1∉C(x1)，则用1改染 xx1，转至情形①．若1∈C(x1)，C(x1)=C{3}，则可假设对于A4中的任一个颜色i都有x1到u的(3，i)-双色路，故A4⊆C(u)∩C(x1)．考虑uw边的染色情况，可分以下2种情况加以讨论：

i)当c(uw)=1时，C(w)=C{3}，C(u)=C{2}，可断言 x1到 w 和 x1到 u无(2，1)-双色路．此时，可用 C({1，2，3}∪{c(yy1)})中的某一色改染 vy，再用1染 vx．

ii)当 c(uw)∈A4时，C(w)=C{1}，C(u)=C{1}，可断言 x1到 w 和 x1到 u 无(2，1)-双色路．此时，可用C({1，2，3}∪{c(yy1)})中的某一色改染vy，再用1染vx，从而可得G的一个无圈k-边染色，与G的极小性矛盾．所以，v不会关联3-面．引理4证毕．

引理5 在3-面的边界上没有2个3-点相邻．

证明 假设一个3-点u与一个3-点v相邻在一个3-面uvw的边界上．设u1≠w，v1≠w分别是u，v的另一邻点，G'=G-uv．由 G 的极小性知，G'有无圈 k-边染色 c，染色集 C={1，2，…，k}，设 c(uu1)=1，c(uw)=2．

1)|C(u)∩C(v)|=0．不妨设 c(vw)=3，c(vv1)=4．

①若 Δ≥4，则用a10∈C(C(u)∪C(v))染 uv．因 |C(C(u)∪C(v))|≥k-4≥1，故这样的颜色a10存在，且染色c仍是无圈的．

②下设 Δ =3，w1是 w 的另一邻点，染色集 C={1，2，3，4}．若3∉C(u1)，则用3 改染 uu1，再用1 染uv;若2∉C(v1)，则用2改染vv1，再用4 染uv．设3∈C(u1)，2∈C(v1)．考虑到c(ww1)的对称性，不妨设c(ww1)=1．若 u1到 w1无(1，4)-双色路，则用4 改染 uw，再用 2 染 uv．否则，设 u1到 w1有(1，4)-双色路，且 4∈C(u1)，4∈C(w1)，C(u1)=C{2}．此时，用 4 改染 uw，2 改染 uu1，再用1 染 uv．

2)|C(u)∩C(v)|=1．

①c(uu1)=c(vw)或c(vv1)=c(uw)．由于这2种情况的证明过程相同，故不妨设c(uu1)=c(vw)=1，c(vv1)=3，A5=C{1，2，3}．可断言对于 A5中的任一个颜色 i都有 u1到 w 的(1，i)-双色路，故 A5⊆C(w)∩C(u1)，且 C(w)=C{3}．若 u1到 v1无(1，3)-双色路，则用3 改染 uw，再用2 染 uv．否则，设 u1到 v1有(1，3)-双色路，且3∈C(u1)，C(u1)=C{2}，1∈C(v1)．又若 A5C(v1)≠Ø，不妨设 4∉C(v1)，则用4改染vv1，再用3染uv．所以设A5⊆C(v1)=C{2}．此时，用2改染vv1，再用3染uv．

②c(uu1)=c(vv1)．不妨设 c(uu1)=c(vv1)=1，c(vw)=3，A5=C{1，2，3}．可断言对于 A5中的任一个颜色i都有u1到v1的(1，i)-双色路，故A5⊆C(u1)∩C(v1)．若3∉C(u1)，则用3改染uu1，转化至情形①．因此，3∈C(u1)，C(u1)=C{2}．若2∉C(v1)，则用 2 改染 vv1，转化至情形①．因此，2∈C(v1)，C(v1)=C{3}．又若 A5C(w)≠Ø，不妨设4∉C(w)，则用4改染 vw，再用3染 uv．所以下设 A5⊆C(w)=C{1}．此时，用3改染vv1，用1改染vw，再用4染 uv．

3)|C(u)∩C(v)|=2．若 c(uu1)=c(uw)，c(vv1)=c(vw)，不妨设 c(uu1)=c(uw)=1，c(vv1)=c(vw)=2，则用a11∈CC(w)染uv，从而可得G的一个无圈k-边染色，与G的极小性矛盾．所以，在3-面的边界上没有2个3-点相邻．引理5证毕．

引理6 若d(v)=5且v相邻3个2-点，则v不与2-点关联在一个3-面中．

证明 假设v与一个2-点u关联在一个3-面uvw中．设x，y是与v相邻的其他的2个2-点，z是v的另一个邻点，x1，y1分别是2-点x，y的另一邻点，G'=G-uv．由G 极小性知，G'有无圈k-边染色c，染色集C={1，2，…，k}．若 c(uw)∉C(v)，则用 a12∈C(C(v)∪{c(uw)})染 uv．否则，c(uw)∈C(v)，不妨设c(vx)=1，c(vy)=2，c(vz)=3，c(vw)=4．

1)若 c(uw)=1，则用 a13∈C(C(v)∪{c(xx1)})染 uv．2)若 c(uw)=2，则用 a14∈C(C(v)∪{c(yy1)})染 uv．3)c(uw)=3．因 d(w)≤Δ，故可记 C(w)中未出现的色为 c0，c0∈C{3，4}．当 c0=1时，用1改染uw，转至情形1);当c0=2时，用2改染uw，转至情形2);当c0∈CC(v)时，直接将c0染uv，从而可得G的一个无圈k-边染色，与G的极小性矛盾．所以，v不与2-点关联在一个3-面中．引理6证毕．

2 定理1的证明

设图G是满足定理1条件的一个边数极小反例．以下将运用Discharging方法导出完成定理1证明所需要的矛盾．

对任意 x∈V(G)∪F(G)，构造一个权函数 ω(x)．其中：当 v∈V(G)时，ω(v)=2d(v)-6;当 f∈F(G)时，ω(f)=d(f)-6．通过权转移，得到一个新的权函数ω'(x)，使得总的权和不变．但对任意的x∈V(G)∪F(G)，有ω'(x)≥0．因此得到-12≥0，即得到了证明定理1所需要的矛盾．．

设v∈V(G)，n2(v)表示与点v相邻的2-点个数，f3(v)表示点v关联的3-面个数．

权转移规则如下：

首先验证 ω'(v)≥0，v∈V(G)．

情形1 v为2-点．由引理1和(R1)知，ω'(v)=2×2-6+1×2=0．

情形2 v为3-点．由权转移规则知v既不转出权也不接受权，故ω'(v)=2×3-6=0．

其次验证 ω'(f)≥0，f∈F(G)．

［1］Fiamcˇík I．The acyclic chromatic class of a graph［J］．Math Slovaca，1978，28(3)：139-145．

［2］Alon N，McDiarmid C，Reed B．Acyclic coloring of graphs［J］．Random Structures Algorithms，1991，2(3)：277-288．

［3］Molloy M，Reed B．Further algorithmic aspects of Lovász local lemma［C］//Proceedings of the 30th Annual ACM Symposium on Theory of Computing held in Dallas．Dallas：ACM，1998：524-529．

［4］Muthu R，Narayanan N，Subramanian C R．Improved bounds on acyclic edge coloring［J］．Discrete Math，2007，307(23)：3063-3069．

［5］Alon N，Sudakov B，Zaks A．Acyclic edge colorings of graphs［J］．Graph Theory，2001，37(3)：157-167．

［6］Alon N，Zaks A．Algorithmic aspects of acyclic edge coloring［J］．Algorithmica，2002，32(4)：611-614．

［7］Cohen N，Havet F，Müller T．Acyclic edge-colouring of planar graphs，Extended abstract［J］．Eletronic Notes in Discrete Math，2009，34(5)：417-421．

［8］Sun Xiangyong，Wu Jianliang．Acyclic edge colorings of planar graphs without short cycles［C］//Proceedings of the 7th International Symposium on Operations Research and Its Applications held in Lijiang．Lijiang：APORC＆CAS，2008：325-329．

［9］Hou Jianfeng，Liu Guizhen，Wu Jianliang．Acyclic edge coloring of planar graphs without small cycles［J］．Graphs andCombinatorics，2011：10．1007/s00373-011-1043-0．

［10］Gao Yunshu，Yu Dongxiao．Acyclic edge coloring of planar graphs without cycles of specific lengths［J］．Appl Math Comput，2011，37(2)：533-540．