伪-海临图的群色数

杨星星，林　永

（宿州学院　数学与统计学院，安徽　宿州　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).去掉图……