楊星星，林　永

（宿州學(xué)院　數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，安徽　宿州　234000）

偽-海臨圖的群色數(shù)

楊星星，林永

（宿州學(xué)院數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，安徽宿州234000）

若圖G=（V，E）,給定方向?yàn)镈,A表示一個(gè)非平凡的且單位元為0的阿貝爾群,F（G，A）表示映射f:E(G)→A的集合.若對(duì)任意f∈F(G,A)存在映射c:V(G)→A,使得G中的每一條有向邊e=uv∈E(G)（方向是u→v）滿足c(u)-c(v)≠f(e),這時(shí)說(shuō)圖G是A-可染的.使得圖G在方向D下是A-可染的,A的最小階數(shù)為圖G的群色數(shù),記為χg(G).本文給出了偽-海臨圖的群色數(shù)不超過(guò)4.

群染色；群色數(shù)；偽-海臨圖

1　基本概念

本文研究的是有限的簡(jiǎn)單圖.設(shè)D(G)表示無(wú)向圖G的一個(gè)方向.為了方便,用D表示D(G).在有向圖G中,邊uv的方向從u指向v,我們稱有向邊uv為弧uv,記為arcuv.

若圖G=(V,E),給定方向?yàn)镈,A表示一個(gè)非平凡的阿貝爾群,F(G,A)表示映射f:E(G)→A的集合.若某一個(gè)f∈F(G,A),存在映射c:V(G)→A且使得任意弧arce=uv∈E(G),c(u)-c(v)≠f(e),稱c是圖G在方向D下的一個(gè)(A,f)-染色.若對(duì)任意的f∈F(G,A)存在(A,f)-染色,這時(shí)說(shuō)圖G是A-可染的.使得圖G在方向D下是A-可染的,A的最小階數(shù)為圖G的群色數(shù),記為χg(G).從文獻(xiàn)[1-3]中我們知道,圖G的群可染性與圖的方向無(wú)關(guān),我們還可以知道χ(G)≤χg(G)（取f=0即可）.

設(shè)H?G,即H是G的子圖.給定f∈F(G,A),如果對(duì)于圖H的一個(gè)(A,f|F(H))-染色c0,在圖G中存在一個(gè)(A,f)-染色c,使得c是c0的一個(gè)擴(kuò)展,我們就說(shuō)c0可以擴(kuò)展為c.如果圖H每一個(gè)(A,f|F(H))-染色c0都可以擴(kuò)展為圖G的一個(gè)(A,f)-染色c,我們就說(shuō)(G,H)是(A,f)-可擴(kuò)展的.如果對(duì)于每一個(gè)f∈F(G,A),(G,H)是(A,f)-可擴(kuò)展的,稱(G,H)是A-可擴(kuò)展的.作者已經(jīng)證明出單圈圖和雙圈圖的群色數(shù)是3和部分雙圖的群色數(shù)[4-5],本文將給出偽-海臨圖的群色數(shù)χg(G)≤4.

設(shè)G(V,E)是一個(gè)2-連通的平面圖,外平面f0的邊界（圈）沒(méi)有弦且d(v)≥3對(duì)任意v∈V(f0).去掉圖G(V,E)中面f0邊界上的所有邊,得到樹圖T,且所有點(diǎn)v∈VV(f0)滿足d(v)≥3,圖G(V,E)叫做偽-海臨圖.點(diǎn)v∈V(f0)且d(v)=3叫做正則點(diǎn),其它面f0上的點(diǎn)叫非正則點(diǎn).所有正則點(diǎn)的集合記為R(f0),非正則點(diǎn)的集合記為IR(f0).

2　相關(guān)引理

引理1[1]任意圖G,χg(G)=2當(dāng)且僅當(dāng)G是一個(gè)森林.

引理2[1]所有的圈Cn(n≥3),χg(G)=3.

引理3[1]設(shè)A是一個(gè)非平凡的阿貝爾群,H?G,如果(G,H)是(A,f)-可擴(kuò)展的,若H是A-可染的,則G也是A-可染的.

引理4[4]設(shè)圖G是一個(gè)單圈圖,則χg(G)=3.

引理5[6]設(shè)圖G是一個(gè)偽-海臨圖(G≠Wp) (Wp是階數(shù)至少是4的輪圖),外平面為f0,p=u1u2…uk是圖G-E(f0)中最長(zhǎng)的路,w∈{u2,uk},則下面情況之一成立:

(1)w是圖G的一個(gè)內(nèi)點(diǎn),N(w)?V(f0),|N(w)I IR (f0)=1,令

N(w)={y,u1,u2,…,um}(m≥2),xu1,yum,uiui+1∈E(f0),

y∈IR(f0),x≠u2,y≠um-1,(i=1,2,…,m-1),

則:G11=G-{w,ui|i=1,2,…,k}+{xy};

G12=G-{ui,ui+1,…,uj}+{ui-1uj+1}(2≤i＜j≤m-1)都是偽-海臨圖.

(2)w是圖G的一個(gè)內(nèi)點(diǎn),|N(w)I(VG)V(f0))|=1,

|N(w)I IR(f0)|=d(w)-1.令N(w)={u,u1,u2,…,um},u是一內(nèi)點(diǎn),ui∈R(f0)(i=1,2,…,m),xu1,yum,uiui+1∈E(f0),(i=1,2,…,m-1),x≠u2,y≠um-1,則圖:G21=G-{u1,u2,…,um} +{xw,yw}都是偽-海臨圖.

3　基本結(jié)論

定理1若圖G是一個(gè)偽-海臨圖,則χg(G)≤4.

證明假設(shè)圖G的方向是D.對(duì)任意f∈F(G,Z4),必須證明出G有(Z4,f)-染色.對(duì)圖G的定點(diǎn)個(gè)數(shù)|V(G)|用數(shù)學(xué)歸納法,令H?,有|H|＜|G|則結(jié)論成立.設(shè)邊wz的方向是從w指向z,邊xu1的方向從x指向u1,uiui+1從ui指向ui+1(i=1,2,…,m-1),yum從um指向y.當(dāng)G=Wp(p≥8),G是Z4-可染的.若G≠Wp,則圖G包含引理5中說(shuō)的點(diǎn)w.故下面的證明分成兩種情況.

C1.w是引理5中的第一種情況

C1.1考慮圖G0=G-{w,ui|i=1,2,…,k}+{xy}.則圖G0是偽-海臨圖且|V(G0)|=n-m-1＜n.根據(jù)歸納假設(shè),G0是(Z4,f)-可染的.定義

c(v)=c0(v)if v∈G0

c(v)=c(w)∈Z4if v=w

c(v)=c(u1)∈Z4-{c(x)-f(xu1),c(w)-f(wu1)}if v=u1

c(v)=c(ui)∈Z4-{c(ui-1)-f(ui-1ui),c(w)-f(wui)}if v=ui(i=1,2,…,m-1);

c(v)=c(um)∈Z4-{c(um-1)-f(um-1um),c(w)-f(wum),c(y)+f (u3y)}if v=um

就把圖G0的 (Z4,f|G0)-染色c0擴(kuò)展為圖G的(Z4,f)-染色c.

C1.2考慮圖G0=G-{u2}+{u1,u3}.則圖G0是一個(gè)偽-海臨圖且|V(G0)|=n-1＜n.根據(jù)歸納假設(shè),G0是(Z4,f)-可染的.由歸納假設(shè)可知,圖G0是Z4-可染的.任意f∈F(G,Z4),c0是一給定的(Z4,f|G0)-染色.定義v=u2.則c是圖G的一個(gè)(Z4,f)-染色.

對(duì)于情況2用類似的方法可證.

我們很容易證明輪圖G=Wp(p是偶數(shù)時(shí))χg(G) =4,也就是說(shuō)這個(gè)界是可達(dá)到的.

〔1〕Lai,H.J.,Zhang,X..Group colorability of graphs[J].Ars Combinatorics(2002)62:299-317.

〔2〕Lai,H.J.,Li,X.W.On group chromatic number of graphs[J].Graphs and Combinatorics2005 (21):469-474.

〔3〕Lai,H.J.,Li,X.W.Group Chromatic number of Planar Graphs of Girth at least4[J].J.Graph Theory(2006)52:51-72.

〔4〕單圈圖和雙圈圖的群色數(shù).宿州學(xué)院學(xué)報(bào)，2012，27（5）:6-7.

〔5〕關(guān)于雙圖的群染色.內(nèi)江師范學(xué)院學(xué)報(bào)，2012（4）:24-26.

〔6〕Meng,X.Y,Miao,L.Y.The Dynamic Coloring Number of Pseudo-Halin graphs[J].Ars Combinatorics,2006,79:3-7.

O157.5

A

1673-260X（2016）09-0004-02

2016-05-13

安徽省教育廳自然科學(xué)研究項(xiàng)目資助（ky2008b253)