伪-海临图的群色数

杨星星，林　永

（宿州学院　数学与统计学院，安徽　宿州　234000）

伪-海临图的群色数

杨星星，林永

（宿州学院数学与统计学院，安徽宿州234000）

若图G=（V，E）,给定方向为D,A表示一个非平凡的且单位元为0的阿贝尔群,F（G，A）表示映射f:E(G)→A的集合.若对任意f∈F(G,A)存在映射c:V(G)→A,使得G中的每一条有向边e=uv∈E(G)（方向是u→v）满足c(u)-c(v)≠f(e),这时说图G是A-可染的.使得图G在方向D下是A-可染的,A的最小阶数为图G的群色数,记为χg(G).本文给出了伪-海临图的群色数不超过4.

群染色；群色数；伪-海临图

1　基本概念

本文研究的是有限的简单图.设D(G)表示无向图G的一个方向.为了方便,用D表示D(G).在有向图G中,边uv的方向从u指向v,我们称有向边uv为弧uv,记为arcuv.

若图G=(V,E),给定方向为D,A表示一个非平凡的阿贝尔群,F(G,A)表示映射f:E(G)→A的集合.若某一个f∈F(G,A),存在映射c:V(G)→A且使得任意弧arce=uv∈E(G),c(u)-c(v)≠f(e),称c是图G在方向D下的一个(A,f)-染色.若对任意的f∈F(G,A)存在(A,f)-染色,这时说图G是A-可染的.使得图G在方向D下是A-可染的,A的最小阶数为图G的群色数,记为χg(G).从文献[1-3]中我们知道,图G的群可染性与图的方向无关,我们还可以知道χ(G)≤χg(G)（取f=0即可）.

设H⊂G,即H是G的子图.给定f∈F(G,A),如果对于图H的一个(A,f|F(H))-染色c0,在图G中存在一个(A,f)-染色c,使得c是c0的一个扩展,我们就说c0可以扩展为c.如果图H每一个(A,f|F(H))-染色c0都可以扩展为图G的一个(A,f)-染色c,我们就说(G,H)是(A,f)-可扩展的.如果对于每一个f∈F(G,A),(G,H)是(A,f)-可扩展的,称(G,H)是A-可扩展的.作者已经证明出单圈图和双圈图的群色数是3和部分双图的群色数[4-5],本文将给出伪-海临图的群色数χg(G)≤4.

设G(V,E)是一个2-连通的平面图,外平面f0的边界（圈）没有弦且d(v)≥3对任意v∈V(f0).去掉图G(V,E)中面f0边界上的所有边,得到树图T,且所有点v∈VV(f0)满足d(v)≥3,图G(V,E)叫做伪-海临图.点v∈V(f0)且d(v)=3叫做正则点,其它面f0上的点叫非正则点.所有正则点的集合记为R(f0),非正则点的集合记为IR(f0).

2　相关引理

引理1[1]任意图G,χg(G)=2当且仅当G是一个森林.

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

引理3[1]设A是一个非平凡的阿贝尔群,H⊆G,如果(G,H)是(A,f)-可扩展的,若H是A-可染的,则G也是A-可染的.

引理4[4]设图G是一个单圈图,则χg(G)=3.

引理5[6]设图G是一个伪-海临图(G≠Wp) (Wp是阶数至少是4的轮图),外平面为f0,p=u1u2…uk是图G-E(f0)中最长的路,w∈{u2,uk},则下面情况之一成立:

(1)w是图G的一个内点,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的一个内点,|N(w)I(VG)V(f0))|=1,

|N(w)I IR(f0)|=d(w)-1.令N(w)={u,u1,u2,…,um},u是一内点,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　基本结论

定理1若图G是一个伪-海临图,则χg(G)≤4.

证明假设图G的方向是D.对任意f∈F(G,Z4),必须证明出G有(Z4,f)-染色.对图G的定点个数|V(G)|用数学归纳法,令H⊆,有|H|＜|G|则结论成立.设边wz的方向是从w指向z,边xu1的方向从x指向u1,uiui+1从ui指向ui+1(i=1,2,…,m-1),yum从um指向y.当G=Wp(p≥8),G是Z4-可染的.若G≠Wp,则图G包含引理5中说的点w.故下面的证明分成两种情况.

C1.w是引理5中的第一种情况

C1.1考虑图G0=G-{w,ui|i=1,2,…,k}+{xy}.则图G0是伪-海临图且|V(G0)|=n-m-1＜n.根据归纳假设,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扩展为图G的(Z4,f)-染色c.

C1.2考虑图G0=G-{u2}+{u1,u3}.则图G0是一个伪-海临图且|V(G0)|=n-1＜n.根据归纳假设,G0是(Z4,f)-可染的.由归纳假设可知,图G0是Z4-可染的.任意f∈F(G,Z4),c0是一给定的(Z4,f|G0)-染色.定义v=u2.则c是图G的一个(Z4,f)-染色.

对于情况2用类似的方法可证.

我们很容易证明轮图G=Wp(p是偶数时)χg(G) =4,也就是说这个界是可达到的.

〔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〕单圈图和双圈图的群色数.宿州学院学报，2012，27（5）:6-7.

〔5〕关于双图的群染色.内江师范学院学报，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

安徽省教育厅自然科学研究项目资助（ky2008b253)