平面图的无圈边染色

王艺桥，舒巧君

（1.北京中医药大学 管理学院，北京 100029；2.杭州电子科技大学 理学院，浙江 杭州 310018）

0 引言

本文考虑有限简单图.给定一个图G，用V（G）和E（G）分别表示它的顶点集和边集.令Ck＝u1u2…uku1是G中长为k的圈.若两个圈至少有一条公共边，就称这两个圈为相邻的.设Δ和δ分别表示一个图G的最大度和最小度.

图G的正常边k染色是指映射c：E（G）→｛1，2，…，k｝，使得相邻的边染不同的颜色.G 的边色数χ′（G）是指使得G是边k可染的最小整数k.无圈边k染色是指G的一个正常的边k染色，使得不产生双色圈.无圈边色数a′（G）是指使得G是无圈边k染色的最小整数k.由著名的Vizing's定理知，Δ≤χ′（G）≤Δ＋1.因此，显然有a′（G）≥χ′（G）≥Δ.Fiamˇcik［1］，Alon等［2］先 后 分 别 提 出 了 著 名 的 无 圈边色数猜想.

猜想1 对任何图G，a′（G）≤Δ＋2.

1991年，Alon等［3］应用概率方法证明了对任何图G，有a′（G）≤64Δ.当前最好的上界a′（G）≤4Δ－4，由Esperet等［4］得到.一些特殊图的无圈边染色已被广泛研究，如最大度为3的图［5］，为4的图［6－7］.对 于 平 面 图 G，Basavaraju 等［8］证 明 了a′（G）≤Δ＋12.Wang等［9］将12降到7，且证明了当G符合以下几个条件之一时，猜想1成立：i）不含3圈［10］；ii）不含4圈［11］；iii）不含5圈［12］；iv）不含3圈和4圈相邻［13］.相关结果参见［14］.

本文旨在研究不含3圈和5圈相邻的平面图的无圈边色数.将证明此类图也是满足猜想1的，这在一定程度上改进了文献［11－12］中的结果和扩充了［13］中的结果.

1 结构分析

给定一个图G，令dG（v）（或d（v））表示顶点v在G中的度.度为k（至少为k，至多为k）的顶点称为k点（k＋点，k－点）.对于平面图H，用F（H）表示其面集合，并用dH（f）（或d（f））表示面f∈F（H）的度.类似地，可定义k面，k＋面以及k－面.对于f∈F（H），用b（f）表示面f的边界，若一个面f沿着某 个 方 向 的 点 依 次 为 u1，u2，…，un，则 记 为f＝［u1u2…un］.

引理1 设G为Δ≥5的2连通平面图，且不含相邻的3圈和5圈，则G含以下子构型A1）～A6）之一（见图1）：

A1）一条路uvw，使得下列之一成立：

A1.1）d（v）＝2且d（u）≤5；

A1.2）d（u）＝d（v）＝3，且x是v的第三个邻点；

A1.3）d（v）＝4且d（u）＝d（w）＝3；

A1.4）d（v）＝3且d（u）＝d（w）＝4；

A1.5）d（v）＝d（x）＝d（y）＝3，d（u）＝4，d（w）＝5，x，y是不同的于v的w 的邻点；

A1.6）d（v）＝3，d（u）＝4，且uw∈E（G）.

A2）一个点u使得d2（u）≥1，d2（u）＋d3（u）≥d（u）－3.设u1，u2，…，ud（u）－1，v 是u 的邻点，满足d（u1）≥d（u2）≥…≥d（ud（u）－1）≥d（v）＝2.设 w 是v的不同于u的邻点.若ui（1≤i≤d（u）－1）是一个2点，则用xi表示不同于u的ui的邻点.于是有下列之一成立：

A2.1）n2（u）＋n3（u）≥d（u）－2；

A2.2）n2（u）＋n3（u）＝d（u）－3，且n3（u）≤1；

A2.3）n2（u）＝d（u）－4，u3u4∈E（G）且对于i＝3，4，n2（ui）＝d（ui）－4；

A2.4）n2（u）＝d（u）－5，d（u4）＝d（u5）＝3且u3u4∈E（G）.

A3）一个3圈uvwu，使得d（u）＝d（v）＝d（w）＝4.

A4）一个5点u相邻于4个3点v，x，y，z以及另一个点w.

A5）一个5点u相邻于x，z，w，y，v且有d（v）＝d（z）＝3以及xv，yv，wz∈E（G）.

A6）一个5点u相邻于x，v，w，y，z且有d（v）＝d（x）＝d（y）＝3，以及xz，yz，wv∈E（G）.

证 假设结论不成立，则G不含子构型A1）～A6）中的任何一个.因G是2连通的，故δ≥2.设G′是移掉G中所有2点后得到的图，H是G′的一个连通分支，则H是连通的不含3圈和5圈相邻的平面图，且对于v∈V（H），v在G中的度至少为3.将H嵌入在平面上.

设u∈V（H），则u∈V（G）.为讨论方便，u在G中的度记为d（u），在H 中的度记为dH（u），在H 中的邻点的集合记为 N′（u）.若dH（u）＝k，令u1，u2，…，uk是u在H 中的邻点，且按顺时针排列，f1，f2，…，fk是与u关联的面，其中f1＝［…u1uu2…］，f2＝［…u2uu3…］，…，fk－1＝［…uk－1uuk…］，fk＝［…ukuu1…］.对于k≥1，令n′k（u）（n′k＋（u），n′k－（u））表示在H中与u相邻的k点（k＋点，k－点）的个数，nk（u）（nk＋（u），nk－（u））表示在G 中与u 相邻的k点（k＋点，k－点）的个数.与面f∈F（H）相关联的k点（k＋点）的个数用nk（f）（nk＋（f））表示.类似地，用mk（u）（mk＋（u））表示在H 中与u 相关联的k面（k＋面）的个数，δ（f）表示与f关联的点的最小度.

因为G不含A1.1），没有5－点会与2点相邻，亦即，若u是满足3≤d（u）≤5的点，则dH（u）＝d（u）.类似地，若d（u）≥6且n2（u）＝0，则dH（u）＝d（u）.又因为G 不含A2.1）和 A2.2），每个6＋点u至多相邻于d（u）－4个2点，这也说明了：若d（u）≥6且n2（u）≥1，则dH（u）≥4，dH（u）＝d（u）－n2（u）.

类似于文献［12］中断言1，2，4，5和文献［11］中断言8的证明，有下面断言1～4成立.

断言1 Δ（H）≥3，对u∈V（H），则n′3（u）＝n3（u）且n2（u）＋n3（u）＝d（u）－dH（u）＋n′3（u）.特别地，若dH（u）＝3，则d（u）＝3.

断言2 若dH（u）＝4且n′3（u）≥1，则d（u）＝4.

断言3 若H中存在一条路uvwx，使得d（u）＝4，d（v）＝d（x）＝3，dH（w）＝5，则d（w）＝5，n3（w）＝2，或者d（w）≥6，n2（w）＝d（w）－5且n3（w）＝2.

断言4 设f＝［uvw］是一个3面，

a）若δ（f）＝3，则n5＋（f）＝2；

b）若δ（f）＝4，则n4＋（f）＝3且n5＋（f）≥1.

断言5 若dH（u）＝5且n3（u）≥3，则

a）d（u）＝5；

b）n3（u）＝3，且对任意的y∈N′（u），x∈N′（y），有d（y）＝3，dH（x）≥5.

证 若d（u）≠5，则n2（u）≥1，n2（u）＋n3（u）＝d（u）－dH（u）＋n3（u）≥d（u）－5＋3≥d（u）－2.因此，G 中就含有 A2.1）.又因为G 不含 A4）和 A1.5），所以，b）成立.

断言6 设u∈V（H），若d（f1）＝3，则对于任意的i∈｛2，k｝，d（fi）＝3或d（fi）≥6.且若dH（u）＝k≥4，则

a）若d（f1）＝d（f2）＝3，则d（f3）≥6，d（fk）≥6.

c）若m3（f）≥1，则m6＋（f）≥2.

用权转移方法来得出矛盾.首先，由欧拉公式｜V（H）｜－｜E（H）｜＋｜F（H）｜＝2和关系式

易得到如下等式：

其次，定义权函数w：对于u∈V（H），w（u）＝2dH（u）－6；对于f∈F（H），w（f）＝dH（f）－6.由（1）可得权和为－12.接下来，将定义权转移规则R1）～R2），且将按此规则对权进行转移.一旦权转移完成，就会产生新的权函数w′.然而，在权转移的过程中，权和是保持不变的.不过可以证明对于所有的x∈V（H）∪F（H）均有w′（x）≥0.这就导出了一个很明显的矛盾

因而证明了这样的反例是不存在的，故引理1成立.

设u是H 中一个度为k的点.令τ（u→f）表示从点u转到与其相关联面f的权的量.权转移规则定义如下：

R2）设k≥5.

R2.1）若d（f）＝5且f＝［…xuy…］，则

R2.2）若d（f）＝4且f＝［vuyx］，则

R2.3）若d（f）＝3，则

设f∈F（H）.由断言6，对于任意的u∈V（H），若d（f1）＝3，则对任意的i∈｛2，k｝，d（fi）＝3或者d（fi）≥6.

假设d（f）＝3，则w（f）＝d（f）－6＝－3.若δ（f）＝3，则由断言4知n5＋（f）＝2.由 R2.3），w′（f）＝－3＋2×＝0.若δ（f）≥4，则由 R）和 R），12.3w′（f）≥－3＋3×1＝0.

假设d（f）＝4且f＝［uvxy］，则w（f）＝d（f）－6＝－2.若δ（f）≥4，则由 R1）和 R2.2）可知，w′（f）≥－2＋4×＝0.因此，下设δ（f）＝3.因G不含 A1.2）和 A1.3），n3（f）≤2.首先假设n3（f）＝2，d（v）＝d（y）＝3，d（u）≥5，d（x）≥5.由 R2.2），w′（v）＝－2＋2×1＝0.否则，n3（f）＝1.不妨设d（v）＝3.因G 不含 A1.4），故max｛d（x），d（u）｝≥5.若d（x）＝4，则由R2.2）或R1），u给f 权1，x，y至少给f权.因此，w′（f）≥－2＋1＋2×＝0.否则，d（u），d（x）≥5，且由 R2.2）或者 R1），u，x 至少给f权，y至少给f权.因此，w′（f）≥－2＋2×＋＝0.

假设d（f）＝5，则w（f）＝d（f）－6＝－1.由R1.1）或 R2.1），b（f）上 的4＋点至少给 f 权.若n＋（f）≥4，则w′（f）≥－1＋4×＝0.否则，因G4不含 A1.2），再由断言1，不妨设f＝［uvwxy］且有d（u）＝d（w）＝3，n4＋（f）＝3.因 G 不含 A1.2）和A1.3），故dH（v）≥5.因此，由 R1）和 R2.1），w′（f）≥－1＋1×＋2×＝0.

假设d（f）≥6，则w′（f）＝w（f）＝d（f）－6≥0.

设u∈V（H）.由断言1可知，dH（u）≥3.若dH（u）＝3，则w′（u）＝w（u）＝2dH（u）－6＝0.下设d（u）≥4.由断言H

假设dH（u）≥9，则

假设dH（u）＝8，则w（u）＝2dH（u）－6＝10且m（u）≤5.若m（u）≤4，则w′（u）≥10－4×－433×1＝0.否则，m3（u）＝5.由断言6，m6＋（u）≥1，故

假设dH（u）＝7，则w（u）＝2dH（u）－6＝8且m（u）≤4.若m（u）≤2，则w′（u）≥8－2×3－5×3321＝0.否则，m3（u）≥3.由断言6，m6＋（u）≥1且w′（u）≥8－4×－（7－1－4）×1＝0.

假设dH（u）＝6，则w（u）＝2dH（u）－6＝6且m3（u）≤4.若m3（u）＝0，则w′（u）≥6－6×1＝0.否则，1≤m3（u）≤4.由断言6，m6＋（u）≥2，因此

假设dH（u）＝4，则w（u）＝2dH（u）－6＝2.若u不与3面关联，则由R）可知w′（u）≥2－4×＝10.否则，下设1≤m3（u）≤2，d（f1）＝3.由断言6，m6＋（u）≥2.因此，由R1），w′（u）≥2－1×2＝0.

假设dH（u）＝5，则w（u）＝2dH（u）－6＝4且m3（u）≤3.只需考虑以下几种子情形.

情况1 m3（u）＝3.由断言6，可设d（f1）＝d（f2）＝d（f4）＝3且d（f3）≥6，d（f5）≥6.因G 不含 A2.4），A5）和 A6），且由断言5知，f1，f2，f4中至多只有两个面的最小度为3.因此，由R2），

情况2 1≤m3（u）≤2.由断言6，m6＋（u）≥2.所以，w′（u）≥min ｛4－2×－（5－2－2）×1，4－－2×1｝ ＝0.

情况3 m3（u）＝0.因G不含 A4）且由断言5，n3（u）≤3，则由对称性，只需讨论以下3种子情形.

3.1）n3（u）＝3.由断言，d（u）＝dH（u）＝5，且对任意的y∈N′（u），当d（y）＝3时，对任意的x∈N′（y），有dH（x）≥5.假设d（u1）＝d（u2）＝d（u3）＝3，则dH（u4）≥4，dH（u5）≥4.因对任意的x∈N′（u1）∪N′（u3）有dH（x）≥5，且由 R2）可知，对任意的fi∈｛f1，f2｝，τ（u→fi）≤1；对任意的fi∈｛f，f｝，τ（u→f）≤；以及τ（u→f）≤.因此，35j4w′（u）≥4－2×1－2×－＝0.假设d（u）＝1d（u2）＝d（u4）＝3，则dH（u3）≥4，dH（u5）≥4.因对任意的x∈N′（u1）∪N′（u2）∪N′（u4）有dH（x）≥5，且由 R2）可知，对任意的fi∈｛f2，f3，f4，f5｝，τ（u→f）≤.因此，w′（u）≥4－1－4×＝0.i

3.2）n3（u）＝2.假设d（u1）＝d（u2）＝3且对任意的ui∈｛u3，u4，u5｝，dH（ui）≥4，则由 R2），对任意的f∈｛f，f｝，τ（u→f）≤.故w′（u）≥4－3×1i34i－2×＝0.假设d（u）＝d（u）＝3且对任意的u13i∈｛u2，u4，u5｝，dH（ui）≥4.因 G 不含 A1.4），u1，u3的邻点中至多只有一个是度为4.因此，由R2），τ（u→f）＋τ（u→f）≤1＋＝，τ（u→f）＋152τ（u→f）≤1＋＝，τ（u→f）≤.故w′（u）≥434－2×－＝0.3.3）n3（u）≤1.由 R2），w′（u）≥4－2×1－3×＝.

2 无圈边色数

本节讨论不含3圈和5圈相邻的平面图的无圈边色数，其中定理的证明需要用到以下几个引理.

引理2［5］若G是Δ≤3的图，则a′（G）≤5.

引理3［6－7］若G 是一个Δ≤4的图，则a′（G）≤6.

假设c是G的一个无圈边k染色，所用的色集为C＝｛1，2，…，k｝.对任意的v∈V（G），用C（v）表示在染色c下与v相邻的边所染的色集合.若一个圈（或路）的边是用i和j进行染色的，则称这样的圈为（i，j）圈（或路）.

定理1 若G是不含3圈和5圈相邻的平面图，则a′（G）≤Δ＋2.

证 对边数｜E（G）｜进行归纳证明.若｜E（G）｜≤Δ＋2，则G显然是无圈边（Δ＋2）可染的.假设G是不含3圈和5圈相邻的平面图，且有｜E（G）｜≥Δ＋3.若Δ≤4，则由引理2，3知结论成立.现假设Δ≥5且G是2连通的.由引理1，G含以下子构型A1）～A6）.易见A1）～A6）均含有一条边满足d（u）＋d（v）≤8或者d（v）＝2.令H＝G－uv，则H 是一个不含3圈和5圈相邻的平面图，且有Δ（H）≥Δ－1≥4.由归纳假设或者引理2或3知，H 有一个无圈边（Δ＋2）染色c，其中所用的色集为C＝｛1，2，…，k｝.因d（u）＋d（v）≤8或d（v）＝2，且｜C｜＝Δ＋2≥max｛7，Δ｝，故C＼（C（u）∪C（v））≠∅.

若C（u）∩C（v）＝∅，则可用C＼（C（u）∪C（v））中的色给uv染色.若对任意的i∈C（u）∪C（v），存在某个j∈C＼（C（u）∪C（v）） ，H 不含（i，j）（u，v）路，则可用j染uv.于是假设

a）C（u）∩C（v）≠∅.

b）对于任意的j∈C＼（ C（u）∪C（v）），存在某个i∈C（u）∩C（v），使得 H 含有（i，j）（u，v）路.

若G 中含 A1），A2.1），A2.2），A2.4），或者 A4）～A6），则如文献［12］中 A1），A2.1）～A2.3），或 A3）～A5）的证明一样，可得到G的一个无圈边染色.若G中含 A2.3）或 A3），则如文献［11］中 A2.3）或 A3）的证明一样，可得到G的一个无圈边染色.

［1］Fiamˇcik F.The acyclic chromatic class of a graph［J］.Math Slovaca，1978，28（2）：139.

［2］Alon N，Sudakov B，Zaks A.Acyclic edge colorings of graphs［J］.J Graph Theory，2001，37（3）：157.

［3］Alon A，McDiarmid C，Reed B.Acyclic coloring of graphs［J］.Random Structures Algorithms，1991，2（3）：277.

［4］Esperet L，Parreau A.Acyclic edge－coloring using entropy compression［J］.European J Combin，2013，34（6）：1019.

［5］Basavaraju M，Chandran L S.Acyclic edge coloring of subcubic graphs［J］.Discrete Math，2008，308（24）：6650.

［6］Basavaraju M，Chandran L S.Acyclic edge coloring of graphs with maximum degree 4［J］.J Graph Theory，2009，61（3）：192.

［7］Wang Weifan，Shu Qiaojun，Wang Yiqiao.Every 4－regular graph is acyclically edge－6－colorable［J］.http：／／arxiv.org／abs／1209.2471v1，to be published.

［8］Basavaraju M，Chandran L S，Cohen N，et al.Acyclic edge－coloring of planar graphs［J］.SIAM J Discrete Math，2011，25（2）：463.

［9］Wang Weifan，Shu Qiaojun，Wang Yiqiao.A new upper bound on the acyclic chromaticindices of planar graphs［J］.European J Combin，2013：34（2）：338.

［10］Shu Qiaojun，Wang Weifan，Wang Yiqiao.Acyclic chromatic indices of planar graphs with girth at least four［J］.J Graph Theory，2013，73（4）：386.

［11］Wang Weifan，Shu Qiaojun，Wang Yiqiao.Acyclic edge coloring of planar graphs without 4－cycles［J］.J Comb Optim，2013，25（4）：562.

［12］Shu Qiaojun，Wang Weifan，Wang Yiqiao.Acyclic edge coloring of planar graphs without 5－cycles［J］.Discrete Appl Math，2012，160（7／8）：1211.

［13］Wang Yiqiao，Shu Qiaojun，Wang Weifan.The acyclic edge coloring of planar graphs without a 3－cycle adjacent to a 4－cycle［J］.Discrete Appl Math，2013，161（16／17）：2687.

［14］Pang Shiyou，Miao Lianying，Qu Jibin，et al.On 3－choosability of planar graphs without certain cycles［J］.徐州师范大学学报：自然科学版，2007，25（4）：8.