2-外平面图的无圈边色数*

舒巧君， 王维凡

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

0 引言

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

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

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

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

猜想1至今还未得到证实，仅知道一些特殊图类满足该猜想．Alon等［5］证明了确定任意图G的无圈边色数是一个NP-问题．关于正则图、平面图、完全二部图等特殊图的无圈边色数研究可参阅文献［6-11］．最近，笔者考虑了大围长平面图的无圈边色数，证明了:若存在(k，m)∈{(3，11)，(4，8)，(5，7)，(8，6)，(12，5)}，使得 Δ(G)≥k，g(G)≥m，则 a'(G)=Δ(G)．

本文研究2-外平面图的无圈边染色问题．一个平面图被称为2-外平面图，如果它能嵌入平面使得其所有顶点出现在至多2个面的边界上．2-外平面图是对外平面图的一种推广．关于2-外平面图的结构性质及相关参数的研究可参阅文献［12-13］．

1 结构性质

先建立2-外平面图的一些结构性质，为无圈边染色做准备工作．

引理1［12］设G是一个连通的2-外平面图，Δ(G)≥5，δ(G)≥2，则G含有下列子结构之一:

(A1)一个2-点相邻于一个8--点;

(A2)一个4-圈v1v2v3v4v1带有一条弦v1v3，使得dG(v2)=dG(v3)=dG(v4)=3;

(A3)一个 4-圈 w1w2w3w4w1带有一条弦 w1w3，使得 dG(w3)=3，dG(wi)≤5，i=1，2，4;

(A4)一个 5-圈 x1x2x3x4x5x1带有 2 条弦 x1x3，x1x4，使得 dG(x3)=dG(x4)=3，dG(xi)≤6，i=1，2，5．

利用引理1，可以证得引理2．

引理2 设G是一个连通的2-外平面图，Δ(G)≥5，δ(G)≥2，则G含有下列子结构之一:

(B1)一个2-点v相邻于点u和w，使得uw∉E(G);

(B2)一个2-点v相邻于点w和一个5--点u，使得uw∈E(G);

(B3)一个2-点v相邻于点w和一个6+-点u，使得uw∈E(G)且n4-(u)≥dG(u)-4;

(B4)一个3-点v相邻于一个3-点u;

(B5)一个 4-圈 w1w2w3w4w1带有一条弦 w1w3，使得 dG(w3)=3，dG(wi)≤5，i=1，2，4．

证明 假设结论不成立，则存在连通的2-外平面图G不含(B1)～(B5)．由假设条件知，δ(G)≥2，Δ(G)≥5．若一个2-点 v相邻于点 u和 w，因 G不含(B1)和(B2)，则必有 uw∈E(G)，且 d(u)≥6，d(w)≥6．更有当2≤d(u)≤5时，有N2(u)=Ø．设H表示去掉G中所有2-点后所得到的图，则H仍是一个连通的2-外平面图，且在G中不与2-点相邻的点在H中的度不变．

设 u∈V(H)，则u∈V(G)且 3≤dG(u)．若 3≤dG(u)≤5，则由 G 不包含(B1)和(B2)，可推出dH(u)=dG(u)．若dG(u)≥6且 n2(u)≥1，则由 G不含(B3)，必有 n4-(u)≤dG(u)-5，亦有 n2(u)≤dG(u)-5．于是n5+(u)≥5，这隐含着dH(u)≥5，说明H不会产生新的4--点．所以，当x∈V(H)时，必有N2(x)=Ø，且H不会含有(B4)．

假设dG(u)≥6且 n2(u)≥1．若 n2(u)≤dG(u)-6，则 dH(u)≥6;若 n2(u)=dG(u)-5，则由n5+(u)≥5可得n5+(u)=5，n3(u)=0．所以dH(u)=5，在H中u不会与3-点相邻，可得 H不会含有(B5)．

综上所得，连通的2-外平面图H不含2-点，且不含(A2)，(A3)和(A4)，这和引理1矛盾，所以假设不成立，即不存在那样的G．引理2证毕．

2 无圈边色数

引理3［11］对每一个 Δ(G)≤4的图G，有a'(G)≤Δ(G)+3．

定理1 若G为2-外平面图，则a'(G)≤Δ(G)+3．

证明 设G是一个2-外平面图．若Δ(G)≤4，则由引理3即可得到结论．假设Δ(G)≥5．对顶点数和边数的和进行归纳证明．若|V(G)|+|E(G)|=11，则结论显然成立．假设G是一个2-外平面图使得|V(G)|+|E(G)|≥12．显然，可以假设G是连通的．若G包含一个1-点v，则子图G-v的任何无圈(Δ(G)+3)-边染色能被扩充到整个图G．于是，假设δ(G)≥2．由引理2知，G至少含有子结构(B1)～(B5)之一．接下来分别处理这5种子图形，并直接应用引理2中的记号．此外，简记Δ=Δ(G)，设C={1，2，…，Δ+3}表示所用的颜色集合，C(v)表示图中与点v所关联的边在某个染色下所用的颜色集合．因为Δ≥5，所以可得|C|=Δ+3≥8．

情形1 G含有(B1) 令H=G-v+{uw}．显然，H仍是一个简单2-外平面图，Δ(H)=Δ．由归纳假设，H有一个无圈(Δ+3)-边染色c．为了将c扩充到到整个图G，令c(uv)=c(uw)，用a∈CC(w)染vw，G中的其他边的颜色与在H中对应的边颜色相同．因|CC(w)|≥Δ+3-dG(u)≥3，故这样的颜色a存在，且染色c仍是无圈的．

情形2G含有(B2) 令H=G-{uv}．由归纳假设，H有一个无圈(Δ+3)-边染色c．若c(vw)∉C(u)，则用 a∈C(C(u)∪{c(vw)})染 uv;若 c(vw)∈C(u)，则用 b∈C(C(u)∪C(w))染 uv．因|C(C(u)∪C(w))|≥Δ+3-(dG(w)+dG(u)-3)≥Δ+3-(Δ+5-3)≥1，故颜色 b存在，且染色 c仍是无圈的．

情形3G含有(B3) 由情形2，可以假设d(u)≥6，d(w)≥6．令H=G-{uv}．由归纳假设，H有一个无圈(Δ +3)-边染色 c．不妨设 C(u)={1，2，…，dG(u)-1}，c(uw)=1，C1(u)={c(ux)|dG(x)≤4}，C2(u)={c(ux)|dG(x)≥5}．因为 v是一个2-点，所以|C1(u)|≥dG(u)-5，|C2(u)|≤4．

若c(vw)∉C(u)，则用 a∈C(C(u)∪{c(vw)})染 uv．否则假设 c(vw)∈C(u)．若存在 b∈(CC(u))C(w)，则用 b染 uv．进一步假设 CC(u)⊆C(w)．因 dG(w)≥6，故推出 1∉C1(u)且|C1(u){1}|=|C1(u)|≥dG(u)-5．

若存在i∈C1(u)C(w)，不妨设c(uu')=i，其中u'是u的一个满足dG(u')≤4的邻点，则用i改染vw，并取j∈(CC(u))C(u')染 uv．特别地，当 c(vw)∈C1(u)时，可以给 uv类似的染色．因为|(CC(u))C(u')|≥Δ+3-(dG(u)-1)-(dG(u')-1)≥Δ+3-(Δ-1)-(4-1)=1，所以颜色 j存在，且染色c仍是无圈的．

现在假设 C1(u)⊆C(w)且 c(vw)∉C1(u)．因1∉C1(u)，c(vw)∈C(u)，(CC(u))∩C1(u)=Ø，故{1，c(vw)}∪(CC(u))∪C1(u)⊆C(w)，又可得|C(w)|≥|{2，c(vw)}∪(CC(u))∪C1(u)|=2+|CC(u)|+|C1(u)|≥2+(Δ +3-dG(u)+1)+(dG(u)-5)=Δ +1，这与|C(w)|≤d(w)≤Δ 矛盾．

情形4 G含有(B4) 设v1，v2≠u是v的另外2个顶点，u1，u2≠v是u的另外2个顶点．令H=G-{uv}．由归纳假设，H 有一个无圈(Δ +3)-边染色 c，不妨设c(vv1)=1，c(vv2)=2．若 1，2∉C(u)，则用a∈C(C(v)∪C(u))染 uv．因|C(C(v)∪C(u))|≥Δ+3-4=Δ -1≥4，故颜色 a存在，且染色c仍是无圈的．

1)若|C(v)∩C(u)|=1，并设 c(uu1)=1，c(uu2)=3，则用 a∈C(C(v)∪C(u)∪C(v1))染 uv．因|C(C(v)∪C(u)∪C(v1))|≥Δ+3-Δ-2=1，故这样的a存在，且染色c仍是无圈的．

2)若|C(v)∩C(u)|=2，并设 c(uu1)=1，c(uu2)=2．因 d(v2)≤Δ，故存在 a∈C(C(v2)∪{1})．若不存在u到v的双色路，则用a染uv．否则，用a改染vv2，然后转化为1)的情形．

情形5 G含有(B5) 不失一般性，假设dG(wi)=5(i=1，3，4)，否则讨论会更简单些．令H=G-{w1w3}．由归纳假设，H 有一个无圈(Δ +3)-边染色 c．不妨设 c(w2w3)=1，c(w3w4)=2，并令 X=C(w2){c(w1w2)，c(w2w3)}，Y=C(w1){c(w1w2)，c(w1w4)}，Z=C(w4){c(w1w4)，c(w3w4)}．显然，|X|=|Z|=3，|Y|=2．由对称性知，只需考虑以下子情形．

1)1，2∉C(w1)．只需用 C(C(w1)∪{1，2})中的某色染 w1w3．

2)1，2∈C(w1)．不妨设 C(w1)={1，2，3，4}，且令 S={5，6，…，Δ +3}．因 c是 H 的无圈边染色，故c(w1w2)=2和c(w1w4)=1不能同时成立．若c(w1w2)=2，则只需用a∈SX染w1w3;若c(w1w4)=1，则有类似的讨论．于是，假设c(w1w2)=4且c(w1w4)=3，亦即Y={1，2}．

若存在 a∈S(X∪Z)，则用 a染 w1w3．于是，假设 S⊆X∪Z．因|X|=|Z|=3且|S|=|{5，6，…，Δ +3}|≥4，故{1，2，3，4}中至多有2 个属于X∪Z．若{1，2，3，4}中没有颜色属于X∪Z，则用3 染w1w3，用S中的某色改染w1w4．假设{1，2，3，4}中至少有1个属于X∪Z，则分下面几种子情形加以讨论:

①假设1，4∈Z．不妨设 Z={1，4，5}，于是 X={6，7，8}，则用6 染 w1w3，3 改染 w2w3．若2，3∈X，则有类似的讨论．

②假设1，4∉Z．不妨设Z={5，6，7}，于是8∈X，则用8 改染 w3w4，{5，6，7}X 中的某色染 w1w3．若2，3∉X，则有类似的讨论．

③假设|{1，4}∩Z|=1 且|{2，3}∩X|=1，此时 Δ =5．不妨设 X={a，5，6}，Z={b，7，8}，其中 a∈{2，3}，b∈{1，4}．当 a=3 时，用5 染 w1w3，7 改染 w2w3;当 b=4 时，有类似的讨论．于是，假设 a=2 且b=1．因此，可用7 染 w1w3，4 改染 w3w4，8 改染 w2w3．

3)1∈C(w1)且2∉C(w1)．不妨设 C(w1)={1，3，4，5}，有 2 种子情形需要考虑:

①c(w1w4)=1．设 c(w1w2)=3，Y={4，5}．若存在 a∈{6，7，…，Δ +3}在 X∪Z 出现至多一次，则用a 染 w1w3;否则推出 Δ =5 且 X=Z={6，7，8}．因此，可用4 改染 w2w3，5 改染 w3w4，2 改染 w1w3．

②c(w1w4)≠1．设 c(w1w2)=3，c(w1w4)=4，Y={1，5}．若存在 a∈{6，7，…，Δ +3}X，则用 a 染w1w3;否则推出 Δ =5 且 X={6，7，8}．此时用 4 改染 w2w3．若存在 b∈{6，7，8}，则用 b染 w1w3;否则推出 Z={6，7，8}．因此，可用1 改染 w3w4，2 染 w1w3．定理 1 证毕．

定理1中的上界Δ(G)+3似乎不是紧的．当最大度较大时不难将这个界改进到Δ(G)+2，从而使猜想1对有较大最大度的2-外平面图成立．因此，证明猜想1对所有2-外平面图成立和回答下面问题是有意义的:

问题1 是否存在一个常数C，使得当一个2-外平面图G满足Δ(G)≥C时，有a'(G)=Δ(G)?

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

［2］Molly M，Reed B．Further aogorithmic aspects of Lovász local lemma［C］//Proceedings of the 30thAnnual ACM Symposium on Theory of Computing Held in Dallas，TX．New York:ACM，1998:524-529．

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

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

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

［6］Něsetril J，Wormald N C．The acyclic edge chromatic number of a randomd-regular graph is d+1［J］．J Graph Theory，2005，49(4):69-74．

［7］Fiedorowics A，Haluszczak M，Narayanan N N．About acyclic edge colourings of planar graphs［J］．Inform Process Lett，2008，108(6):412-417．

［8］Hou J，Wu J，Liu G，et al．Acyclic edge colorings of planar graphs and series-parallel graphs［J］．Sci China Ser:A Math，2009，51(3):605-616．

［9］Borowiecki M，Fiedorowics A．Acyclic edge colouring of plananr graphs without short cycles［J］．Discrete Math，2010，310(9):1445-1455．

［10］Basavaraju M，Chandran L S．A note on acyclic edge coloring of complete bipartite graphs［J］．Discrete Math，2009，309(13):4646-4648．

［11］Basavaraju M，Chandran L S．Acyclic edge coloring of graphs with maximum with degree 4［J］．J Graph Theory，2009，61(3):192-209．

［12］汤宇翔，王维凡．2-外平面图的 L(2，1)-标号数［J］．浙江师范大学学报:自然科学版，2009，32(1):40-44．

［13］孔立，张秀丽．双外平面的全染色［J］．山东轻工业学院学报，2005，19(2):81-84．