平面图的无圈边染色

段娟娟,丁　伟

(中国矿业大学 理学院,江苏 徐州　221116)

0　引言

1　平面图的无圈边色数

引理1如果图G是最大度为3的非正则的连通图,则Xa′(G)≤4.

此定理的证明文[4]中已经给出了证明,在此我们就不再叙述.

定理1设图G是简单图,如果有g(G)≥4,则有Xa′(G)≤Δ(G)+4

定义1我们首先要了解图的最大平均度的定义,在文[8]中定义了一个图的最大平均度:

引理2如果图G的Mad(G)<4,且δ(G)≥2,则图G至少包含下面几种情况之一.

情况1一个2度点至少邻接一个度数小于等于4的点;

情况2一个3度点至少邻接一个小于等于4度的点和一个5度的点;

情况3一个4度点至少邻接一个2度点;

情况4一个5度点至少邻接一个2度点和一个3度点;

情况5一个5度点至少邻接4个3度点;

情况6一个6度点至少邻接邻接5个3度点,和一个度数小于等于Δ(G)-1;

情况7一个7度点邻接7个3度点;

情况8一个点x当d(x)≥6时,点x至少邻接d(x)-3个2度点其中的一个可以是3度点.

A) 如果x是2度点或3度点时,则点x不转移任何值给邻接的点;

证明假设图G是不满足定理成立的最小反例,设图G是Δ(G)≥3,2-连通的图,即图G的δ(G)≥2.设k=Δ(G)+4,令l={1,2,3,…,k}是图的颜色集合.由引理1知道图G中至少包含上面的8中情况之一则我们分别来讨论图G的8种情况.

情况1设x是一个2度点,邻接一个4度点y,z是x的另外一个邻点.让H=G-xy由图G的最小性可知,C是图H的一个无圈k染色,有Xa′(H)≤k.如果|C(x)∩C(y)|=0时,对边xy染颜色α∈l{C(x)∪C(y)},则可以得到图G的一个无圈k染色.如果|C(x)∩C(y)|=1时,|C(y)∪C(z)|=3+Δ-1=Δ+2,则对边xy染颜色α满足α∈l{C(y)∪C(z)},则可得到图G的一个无圈边染色.

情况2设x是一个3度点,邻接一个4度点y,一个5度点y1,z是x邻接的另外一个点让H=G-xy,则由图G的最小性知,C是图H的一个无圈k染色.在图中设C(xz)=1,C(xy1)=2,如果|C(x)∩C(y)|=0时,对边xy染颜色α∈l{C(x)∪C(y)}则可以得到图G的一个无圈k染色.如果|C(x)∩C(y)|=1时,如果1∈C(y)时,则有图G|C(y)∪C(z)∪C(xy1)|≤Δ+3,则对边xy染颜色α∈l{C(z)∪C(y)∪C(xy1)},α∉C(z),2∈C(xy1)∉C(y),则可以得到图G的一个无圈k染色.如果2∈C(y)时,则有图G满足|C(y)∪C(y1)∪C(xz)|≤Δ+3,则对边xy染颜色α∈l{C(y)∪C(y1)∪C(xz)}且有α∉C(y1),2∈C(xz)∉C(y),则可得到图G的一个无圈k染色.

如果|C(x)∩C(y)|=2时,C(x)={1,2}∈C(y),若1=C(xz)∉C(y1)则有图G满足,则对边C(xy1)染颜色α∈l{C(y)∪C(y1)∪C(x)},则可以得到图H的无圈k染色C′,此时有|C′(x)∩C′(y)|=|C(x)C(y)|=1则由上面的证明我们可以得到图G的一个无圈k染色.若2=C(xy1)∉C(z),既可以对边xz重新染颜色α∈l{C(y)∪C(z)∪C(x)},则可以得到图H的一个无圈k染色C″,有|C″(x)∩C″(y)|=|C(x)∩C(y)|=1,由上面的证明既可以得到图G的无圈k染色.若有1=C(xz)∈C(y1),2=C(xy1)∈C(z)如果有C(z)∩C(y1)=C(y)∩C(z)=C(y)∩C(y1)={1,2}否则,可以对边xy染颜色α满足α∈l{C(y)∪C(z)∪C(y1)},可以得到图G的一个无圈k染色.不是一般性我们可以假设C(y)={1,2,3},C(y1)={1,2,4,5,6},C(y)={1,2,7，…,k},则可以对边xy1染颜色7,对边xz染颜色3,则可得到图H的一个无圈k染色C‴,则得到|C‴(x)∩C‴(y)|<|C(x)∩C(y)|,根据上面的证明我们既可以得到图G的一个无圈k染色.

情况3设x是一个4度点,y是x邻接的一个2度点,yi(i=1,2,3)是x邻接的其他度点.设H=G-xy,由图G的最小性可知,C是图H的一个无圈k染色.不妨设C(xyi)=i,(i=1,2,3).如果|C(x)∩C(y)|=0时,对边xy染颜色α∈lC(x)∪C(y),即可得到图G的一个无圈k染色.如果|C(x)∪C(y)|=1,不妨设C(xy1)=C(yu)=1,及可以对边xy染颜色α∈lC(x)∪C(y1)∪C(y),因为|C(x)∪C(y1)∪C(y)|≤Δ+2,我们既可以得到图G的一个无圈k染色.

情况4设x是一个5度点,则x邻接的2度点设为y,u是y异于x的另外一个邻点.邻接的3度点是y1,邻接的其它度点是zi,(i=1,2,3),有图G的最小性可以得到,可以得到图H是一个无圈k染色,不是一般性可设C(xy1)=4,C(xzi)=i,(i=1,2,3).若果|C(x)∩C(y)|=0,则可以对边xy染颜色α∈l{C(x)∪C(y)},及可以得到图G的一个无圈k染色.如果|C(x)∩C(y)|=1,若C(yu)=4,则我们可以选择α∈l{C(x)∪C(y)∪C(y1)}去染边xy则可得到图G的一个无圈k染色.不是一般性我们可以假设C(yu)=1,则可以对边xy染颜色α∈l{C(x)∩C(y)∩C(z1)},因为我们有C(x)∩C(y)∩C(z1)≤Δ+3即可以得到图G的一个无圈k染色.

情况5设x是一个5度点,则x邻接的4个3度点分别是y,y1,y2,y3,其中ui,vi是点yi异于x的其它邻点,(i=1,2,3)z是x的另外一个邻点.让H=G-xy,有图G的最小性可以得到,可以得到图H是一个无圈k染色,不失一般性,可以假设C(xz)=4,C(xyi)=i(i=1,2,3).如果|C(x)∩C(y)|=0,则可以对边xy染颜色α∈l{C(x)∪C(y)},及可以得到图G的一个无圈k染色.如果|C(x)∩C(y)|=1,不是一般性我们可以假设5∈C(y).若C(y)={1,5},则我们可以选择α∈l{C(x)∪C(y)∪C(y1)}去染边xy,则可得到图G的一个无圈k染色.因为|C(x)∪C(y)∪C(y1)|≤Δ+3.若C(y)≠{1,5},我们可以假设C(y)∩{1,2,3}=φ,因此C(y)={4,5}.如果颜色α∈{6,7,…,k}C(z),则可以对边xy染颜色α即可得的图G的一个无圈k染色.当{6,7,8，…,k}∈C(z),因为C(xz)=4,以得到C(z)={4,6,7，…,k},d(z)=Δ.若存在某个yi,(i=1,2,3),有C(yi)≠5,我们既可以交换C(xz)与C(xyi)的颜色,得到图H的一个无圈k染色C′,有|C′(x)∩C′(y)|=0,则有|C′(x)∩C′(y)|<|C(y)∩C(x)|=1,我们可以对边xy染颜色α∈l{C′(x)∪C′(y)∪C′(yi)},既可以得到图G的一个无圈k染色.若对所有的yi都有(i=1,2,3),C(yiui)=5,我们很容易得到存在β∈{6,7,…,k}有对所有的C(yivi)≠β,(i=1,2,3),则我们可以重新对边xz染颜色1,对边xy1染颜色β,既可以得到图H的一个无圈k染色C″,有C″(x)∩C″(y)=φ,那么我们有上面的证明既可以得到图G的一个无圈k染色.

情况6图G包含一个6-点邻接五个3--点和一个小于或等于(Δ-1)--点.

设x是图G的一个6-点,它邻接的五个3--点分别为v,v1,v2,v3,v4,其(Δ-1)--邻点为y.设si,ti分别为顶点vi(i∈{1,2,3,4})的除x以外的两个邻点,设G′=Gxv,则由图G的最小性知G′存在一个k-无圈边染色π.我们不妨设其染色为π(xv1)=1,π(xv2)=2,π(xv3)=3,π(xv4)=4,π(xy)=5,则:

(A) 如果|π(x)∩π(v)|=0,则我们可以从C{π(x),π(v)}中选取一种颜色染边xv.从而得到图G的一个k-无圈边染色.

(B) 如果|π(x)∩π(v)|=1,我们不妨设6∈π(v),当π(v)={1,6}时,因为Δ(G)≥6,从而|π(x)∪π(v)∪π(WG′(x,v))|≤8

如果存在一个顶点vi(i∈{1,2,3,4})使得π(vi)π(xvi)⊆{6,7,8,…,k},则我们可以交换边xvi和边xy所染的颜色而得到图G′的一个新的k-无圈边染色,此时问题即转化为上一种情况.从而对任意顶点vi(i∈{1,2,3,4}),一定存在至少一种颜色α,使得α∈π(vi)π(xvi)且α∈{1,2,3,4,5}π(xvi).如果存在一个顶点(不妨设为v1)使得5∉π(v1),则颜色集{2,3,4}中至少有一种颜色在顶点v1表现.当v1仅表现颜色集{2,3,4}中的一种颜色(不妨设为2)时,此时存在一种颜色α∈{6,7,8,…,k}{π(v1)∪π(v2)},使得边xv1染上颜色α,边xv染上颜色1能够成图G的一个k-无圈边染色.当顶点v1表现了颜色集{2,3,4}中的两种颜色(不妨设π(v1)={2,3})时,此时亦存在一种颜色α∈{6,7,8,…,k}{π(v2)∪π(v3)},使得边xv1染上颜色α,边xv染上颜色1能够成图G的一个k-无圈边染色.从而对任意顶点vi(i∈{1,2,3,4}),都有5∈π(vi).同时我们可以得到一定存在一种颜色α∈{6,7,8,…,k}使得对任意顶点vi(i∈{1,2,3,4}),α∉π(vi).我们将边xv1染上颜色α,xy染上颜色1可构成图G′的一个新的k-无圈边染色,此时问题即转化为前一种情况.

(C) 如果|π(x)∩π(v)|=2,如果π(x)∩π(v)={1,2}或{1,3}或{1,4}或{2,3}或{2,4}或{3,4}时,我们有|π(x)∪π(v)∪π(WG′(x,v))|≤9

因为d(y)≤Δ(G)-1,从而存在一种颜色α∈{6,7,…,k}使得α不在顶点y表现,不妨设其为颜色6,如果6∉π(v1),则我们可将边xv染上颜色6而得到图G的一个k-无圈边染色,从而6∈π(v1).我们不妨设π(v1s1)=6,如果π(v1t1)∉{2,3,4,5},则一定存在一种颜色α∈C{1,2,3,4,5,6,π(v1t1)},使得边xv1染上颜色α后仍是图G′的一个k-无圈边染色,此时问题即转化为情况6(B).从而π(v1t1)∈{2,3,4,5},当π(v1t1)=2时,我们可以找到一种颜色α,使得α∈C{1,2,3,4,5,6,π(v2s2),π(v2t2)}且当边xv1重新染上颜色α后仍是图G′的一个k-无圈边染色,此时问题即转化为情况6(B).当π(v1t1)=3或4时,亦可由π(v1t1)=2时类似的证明将其问题转化为情况6(B).当π(v1t1)=5时,如果存在一种颜色α∈{7,8,…,k}使得α不在顶点y表现,则我们可将边xv1重新染上颜色α而构成图G′的一个k-无圈边染色,此时问题即转化为情形6(2).否则π(y)={5,7,8,…,k}且d(y)=Δ(G)-1,此时我们将边xy重新染上颜色6亦可得到图G′的一个k-无圈边染色,此时问题即转化为情况6(B).

情况7设x是一个7度点,邻接7个度为3度的点,设x的邻点分别为vi,i=1,2,…,7,让图H=G-xv7,由图G的最小性可知,C是图H的一个无圈k.我们不防设边C(xvi)=i,i=(1,2,…,6),若|C(x)∩C(v7)|=0则可以对边xv7染颜色α∈l{C(x)∩C(v7)},既可以得到图G的一个无圈k染色.若|C(x)∩C(v7)|=1,不使一般性可以假设C(v7)∈{1,7},因为|C(x)∪C(v1)∪C(v7)|≤9,Δ≥7,则可以对边xv7染颜色β∈l{C(x)∩C(v7)∩C(v1)},则可以得到图G的一个无圈k染色.|C(x)∩C(v7)|=2,不使一般性可以假设C(v7)∈{1,2},因为|C(x)∪C(v1)∪C(v2)|≤10,Δ≥7,则可以对边xv7染颜色γ∈l{C(x)∩C(v2)∩C(v1)},则可以得到图G的一个无圈k染色.

情况8设x是图G的一个点,且点x的度数大于等于7时,x至少邻接d(x)-3个2度点,其中一个可以是3度点.不妨设x的2度邻点分别为y,yi(i=2,3,…,d(x)-3),v1是定点y的另外一个邻点,其中一个可以是3度点.z1,z2,z3为剩下的3个点.让H=G-xy,由图G的最小性可知,C是图H的一个无圈k.可以设xyi染颜色{i},{i=2,3,…,d(x)-3},则边xzi分别染颜色{i=d(x)-2,d(x)-1,d(x)}若|C(x)∩C(y)|=0,则可以对边xy染颜色α∈l{C(x)∪C(y)},则可以得到图G的一个无圈k染色.若果|C(x)∩C(y)|=1时,若边yv1∈{2,3,…,d(x)-3}设C(yv1)=2,则让边xy染颜色β∈l{C(x)∪C(y2)}我们即可得到图G的一个无圈k染色.如果yv1∈{d(x)-2,d(x)-1,d(x)},因为d(v1)≤Δ,而且k=Δ+4,则对边yv1染颜色γ∉{C(v1),d(x)-2,d(x)-1,d(x)},则可以得到图H的一个无圈k染色C′,则根据前面的证明即可得到图G的一个无圈k染色.

在上面的情况的证明中我们得到图G的一个无圈k染色,与假设矛盾.所以我们即可以得到定理一是成立的.

由引理2,及性质1,既可以证明定理2是成立的.

参考文献：

[1]West D B.Tntroduction to Graph Theory[M]．Prentice Hall,Upper Saddle River,2001.

[2]Alon N,Sudakov,Zaks A. Acycle coloring of graphs[J]．J GraphTheory,2001,37:157-167.

[3]Alon N,McDiarmid C J H,Reed B A.Acycli coloring of graphs[J]．Random Structures Algorithms,1991,2:277-288.

[4]Basavaraju,Chandran L S. Acyclecoloring of subcubic graphs[J]．Discrete Math,2008,308: 6650-6653.

[5]Fiedorowicz A,Haluszczak M,Naraynan N. About acyclic edge colourings of planar graphs[J]．Tnform Process Lett,2008,108:412-417.

[6]Mieczyslaw,Borowiecki,Anna. Fiedorowicz,Acyclic dege colouring of planar graphsWithout short cycles[J]．Tn Faculty of Mathematic,Computer Science and Econometrics,University of Zielona Gora,Z,Szafrana 4a:65-516.

[7]Wei D,Xu B B.Some results on acyclic edge coloring of piane graphs[J]．Information Processing Letters,2010,110: 887-892.

[8]Montassier M,Ochem P,Raspaud A. On the acyclic choosability of graphs[J]．J.Graph Theory,2006,51:281-300.

[9]Molloy M,Reed B. Futher algorithmic aspects of the local lemma[J]．Tn Proceedings of the 30thAnnual ACM Symposium on Theoy of Computing,1998:524-529.

[10]Muthu R,Narayanan ,Subramanian C R. Optimal acycle edge colouring of grid like graphs[J]．TnComputing and Combinatorics,12th COCOON,Taipei,Taiwan,2006,4508:144-152.

[11]Muthu R,Narayanan,Subramanian C R. Acyclic edge colouring of outerplanar graphs[J]．TnAlgorithmic Aspects in Tnformation and Management 3th AAIM Portlang,USA,2007,4508:144-152.

[12]Skulrattanakulchai S. Acyclic coloring of subcubic graphs[J]．Tnform Process Lett,2004,92:161-167.