平面图的动态着色

林 越, 赵克文

(琼州学院数学系 海南三亚572022)

平面图的动态着色

林 越, 赵克文

(琼州学院数学系 海南三亚572022)

研究平面图的动态着色数,通过定义一个算法得到强导出图.利用颜色对换的思想来研究平面图动态着色的上界问题,得到结论:若G是平面图,则χd(G)≤5.

算法;强导出图;动态着色

0 引言

图的着色理论在图论中占有重要地位,其结论有着广泛的应用.关于图G=(V,E),v∈V(G)的顶点度定义为图G中与v关联的边的数目,记为dG(v),v的邻域记为N(v).图G的正常k顶点着色,简称图的k顶点着色,用k种颜色对G的各顶点进行着色,使得任意相邻的2点着不同的颜色.若G至少有1个正常k顶点着色,就称G是正常k点可着色的.使G是k点可着色的数k的最小值称为图G的色数,记为χ(G)= k,则称G为k色图.图G的动态k着色是一个映射c:V(G)→C(k)={1,2,…,k},满足:①如果uv∈E(G),则c(u)≠c(v);②对∀v∈V(G),|c(N(v))|≥m in{2,dG(v)}.可以正常(k,2)着色的最小k为G的动态着色数,记为χd(G).本文所研究的图除特别说明外,均为简单有限连通图,文中没给出的定义或术语可参考文献[1].

文献[2]首次提出了动态着色的概念;文献[3]中讨论了一些关于动态着色的性质,并证明一般图的χd(G)≤Δ+3;文献[4]研究了Pseudo-Halin图的动态着色;文献[5]研究了单圈图和双圈图的动态色数,并得到它们的动态色数是3或4;文献[6]研究了没有分支和C5同构的图的动态着色.本文主要讨论平面图动态着色的上界问题,得到定理1,即若G是平面图,则χd(G)≤5.

1 预备知识

在经典“平面图是5可顶点着色的”证明过程中,先找图G的i色顶与j色顶的导出子图Gi,j:i色与j色交替出现的一条轨道,然后对换该导出子图的i色与j色,不影响图G的正常着色.

把这一思想运用到“平面图是5可动态着色的”中来,首先找图G的i色顶与j色顶强导出图Hi,j:从任一着i色顶点v1开始,检查其邻域N(v1),若存在着j色的顶v2,那么把v1,v2看成Hi,j的2个顶点,把v1, v2看成Hi,j的一条边,接着继续检查v2的邻域N(v2),重复下去,直到对于vk(vk着i色或者j色之一,不妨设vk着j色)来说,在其邻域N(vk)中已经不存在与其相邻并且着i色顶点,否则可以继续重复下去,又因为本身着j色,当然也不存与其相邻并且着j色顶点.这时检查vk邻域中的任一点vl,若满足在NG(vl)-vk中任一顶点都着i色,连接其中着i色的一点vk+1,把vk+1并入Hi,j已有的顶点集,把vkvk+1并入Hi,j已有的边集,然后又从vk+1开始检查其邻域,直到不能进行下去为止.显然,Hi,j也是i色与j色交替出现的一条轨道.

根据以上思想,给出强导出图算法具体步骤如下:

若已存在=G(V,E)的一个顶点着色c,记c(i)={v|c(v)=i,v∈G}.

Step1设Hi,j=(V′,E′),V′=∅,E′=∅.

Step2设v0∈c(i),若不存在与其相邻并且着j色的顶点,转Step3;若存在与其相邻且着j色的顶点v1,V′∶=V′∪{v0,v1},E′∶=E′∪{v0v1},i∶=j,重复Step2直到不存在这样的顶点,结束.这时把最后一个并入V的顶点记为vk,vk着i色或者j色之一,不妨设vk着j色.

Step3若不存在顶点vl,满足在NG(vl)-vk中任一顶点都着i色,结束.若存在这样的顶点vl,V′∶= V′∪{v′l},E′∶=E′∪{vkv′l},其中v′l为NG(vl)-vk中着i色的任一顶点.转Step2.

通过以上作法得到的图称为i色顶和j色顶的强导出图,记为Hi,j.在Step3中,选取的v′l为NG(vl)-vk中着i色的任一顶点,那么很显然Hi,j不唯一.

命题1如果图G是平面图,那么构造Hi,j时添加的边得到G′仍然是平面图.

证明由构造Hi,j的作法,所添加的边是vkv′l,其中v′l为NG(vl)-vk中都着i色的任一顶点,只需考虑添加的边是否会破坏图G的平面性即可.若存在NG(vl)-vk中的某一顶点与vk在同一个圈的内部,那么添加边vkv′l后,不破坏图G的平面性.若NG(vl)-vk全都在有一个圈C内部,而vk在这个圈的外部,可以断定vl位于圈C上,所以必还有一顶v′l位于圈C上,又假设vk位于C的外部,所以添加边vkv′l后也不会破坏图G的平面性,G′=G+{vkv′l}仍然是平面图.证毕.

命题2若已对平面图G进行动态着色,对换图Hi,j中i,j两种颜色不影响图G的动态着色.

证明由Hi,j的作法,Hi,j是一i色与j色交替出现的子图,且由Step3可知,交换后能保证每个顶点的邻域至少能着2种颜色的动态着色性质不变.证毕.

2 定理1的证明

现在证明引言中提出的定理1.

证明设G是连通平面图,对G的顶点数n进行归纳证明.

当n≤5时,定理显然成立.假设n≤k-1时定理1已成立,只要证明n=k时定理也成立即可.

由于G是平面图,δ≤5,设d(v0)≤5.

记G1=G-v0+xy,其中,x,y分别为N(v0)中的任意2个顶点,若已存在这样的一条边则不再连接.

若d(v0)≤4,由归纳假设χd(G1)≤5,即G1中已用5种颜色动态着色,再把v0与它在G中的邻域集(不超过4个)相异的颜色着色,可知,对于v0点也满足动态着色的定义,其他点不影响,所以d(v0)≤5.

若d(v0)=5,设v1,v2,v3,v4,v5是v0的邻顶点,不妨设v1,v2,v3,v4,v5依顺时针排列(不然重新对这5个顶点编号).由归纳假设χd(G1)≤5,设G1已用5种颜色1,2,3,4,5动态着色,且v1,v2,v3,v4,v5在G1中上的色分别是1,2,3,4,5,考虑H1,3.

(1)若v1与v3分别居于2个连通分支中,在含v1的连通分支中交换1色和3色,由命题2知不影响动态着色,在G中把v0上1色即得G的用5种颜色的动态着色,所以d(v0)≤5.

(2)若v1与v3同在一个H1,3的连通分支中,则在G1中存在轨P(v1,v3),此轨道上的1色与3色交替出现.考虑H2,4,若v2与v4分属于2个连通分支中,与(1)相似,可得d(v0)≤5.而v2与v4不会出现在H2,4的同一个连通分支中,不然存在轨P(v2,v4),其上的顶2色与4色交替出现,但在G中,有一个圈C0:v0v1P (v1,v3)v3v1.于是P(v1,v3)与P(v2,v4)必有公共顶点,这个公共顶点P(v1,v3)要求它是1色或者3色,而P(v2,v4)要求它是2色或者4色,这是不可能的.证毕.

3 结束语

动态着色是正常着色的一种“衍生物”,它有着广泛的应用.几类特殊图和平面图的动态着色的上界已经研究清楚了,而一般图的动态着色的上界到目前为止还没有明确的结论,这也是动态着色问题的难点之一.

参考文献:

[1] Bondy J A,M urty U SR.Graph Theory with App lications[M].Macmillan:North-Holland Elservie,1976.

[2] Montgomery B.Dynamic colo ring[D].West Virginia:West Virginia University,2001:25-37.

[3] Lai H J,Montgomery B,Poon H.Upper bounds of dynamic chromatic number[J].A rs Combinatoria,2003,68(3): 193-201.

[4] Meng X Y,M iao L Y,Su B T,et al.The dynamic coloring numbers of Pseudo-Halin graphs[J].A rs Combincto ria, 2006,79:3-10.

[5] 秦健,张岩.单圈图和双圈图的动态色数[J].山东大学学报:理学版,2007,42(10):37-40.

[6] Akbari S,Ghanbari M,Jahanbekam S.On the list dynamic coloring of graphs[J].Discrete App lied Mathematics,2009, 157(14),3005-3007.

Dynam ic Coloring for Planar Graph

L IN Yue, ZHAO Ke-w en
(Department of M athem atics,Qiongzhou University,Sanya 572022,China)

A dynamic coloring fo r p lanar graph is mainly discussed.An induced graph,obtained by defining an algorithm,is used to study the upper bounds of dynamic chromatic number of the p lanar graph.And,the conclusion is:if G is p lanar,thenχd(G)≤5.

algo rithm;induced graph;dynam ic colo ring

TP 301.5

A

1671-6841(2010)03-0034-03

2010-04-01

海南省自然科学基金资助项目,编号10501.

林越(1981-),男,助教,硕士,主要从事图论与算法研究,E-mail:linyue_306@163.com;通讯联系人:赵克文(1964-),男,教授,主要从事图论研究,E-mail:kewen.zhao@yahoo.com.cn.