平面圖的動態(tài)著色

林 越, 趙克文

(瓊州學院數(shù)學系 海南三亞572022)

平面圖的動態(tài)著色

林 越, 趙克文

(瓊州學院數(shù)學系 海南三亞572022)

研究平面圖的動態(tài)著色數(shù),通過定義一個算法得到強導出圖.利用顏色對換的思想來研究平面圖動態(tài)著色的上界問題,得到結論:若G是平面圖,則χd(G)≤5.

算法;強導出圖;動態(tài)著色

0 引言

圖的著色理論在圖論中占有重要地位,其結論有著廣泛的應用.關于圖G=(V,E),v∈V(G)的頂點度定義為圖G中與v關聯(lián)的邊的數(shù)目,記為dG(v),v的鄰域記為N(v).圖G的正常k頂點著色,簡稱圖的k頂點著色,用k種顏色對G的各頂點進行著色,使得任意相鄰的2點著不同的顏色.若G至少有1個正常k頂點著色,就稱G是正常k點可著色的.使G是k點可著色的數(shù)k的最小值稱為圖G的色數(shù),記為χ(G)= k,則稱G為k色圖.圖G的動態(tài)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的動態(tài)著色數(shù),記為χd(G).本文所研究的圖除特別說明外,均為簡單有限連通圖,文中沒給出的定義或術語可參考文獻[1].

文獻[2]首次提出了動態(tài)著色的概念;文獻[3]中討論了一些關于動態(tài)著色的性質(zhì),并證明一般圖的χd(G)≤Δ+3;文獻[4]研究了Pseudo-Halin圖的動態(tài)著色;文獻[5]研究了單圈圖和雙圈圖的動態(tài)色數(shù),并得到它們的動態(tài)色數(shù)是3或4;文獻[6]研究了沒有分支和C5同構的圖的動態(tài)著色.本文主要討論平面圖動態(tài)著色的上界問題,得到定理1,即若G是平面圖,則χd(G)≤5.

1 預備知識

在經(jīng)典“平面圖是5可頂點著色的”證明過程中,先找圖G的i色頂與j色頂?shù)膶С鲎訄DGi,j:i色與j色交替出現(xiàn)的一條軌道,然后對換該導出子圖的i色與j色,不影響圖G的正常著色.

把這一思想運用到“平面圖是5可動態(tài)著色的”中來,首先找圖G的i色頂與j色頂強導出圖Hi,j:從任一著i色頂點v1開始,檢查其鄰域N(v1),若存在著j色的頂v2,那么把v1,v2看成Hi,j的2個頂點,把v1, v2看成Hi,j的一條邊,接著繼續(xù)檢查v2的鄰域N(v2),重復下去,直到對于vk(vk著i色或者j色之一,不妨設vk著j色)來說,在其鄰域N(vk)中已經(jīng)不存在與其相鄰并且著i色頂點,否則可以繼續(xù)重復下去,又因為本身著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色交替出現(xiàn)的一條軌道.

根據(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色的頂點,轉(zhuǎn)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色的任一頂點.轉(zhuǎn)Step2.

通過以上作法得到的圖稱為i色頂和j色頂?shù)膹妼С鰣D,記為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在同一個圈的內(nèi)部,那么添加邊vkv′l后,不破壞圖G的平面性.若NG(vl)-vk全都在有一個圈C內(nèi)部,而vk在這個圈的外部,可以斷定vl位于圈C上,所以必還有一頂v′l位于圈C上,又假設vk位于C的外部,所以添加邊vkv′l后也不會破壞圖G的平面性,G′=G+{vkv′l}仍然是平面圖.證畢.

命題2若已對平面圖G進行動態(tài)著色,對換圖Hi,j中i,j兩種顏色不影響圖G的動態(tài)著色.

證明由Hi,j的作法,Hi,j是一i色與j色交替出現(xiàn)的子圖,且由Step3可知,交換后能保證每個頂點的鄰域至少能著2種顏色的動態(tài)著色性質(zhì)不變.證畢.

2 定理1的證明

現(xiàn)在證明引言中提出的定理1.

證明設G是連通平面圖,對G的頂點數(shù)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種顏色動態(tài)著色,再把v0與它在G中的鄰域集(不超過4個)相異的顏色著色,可知,對于v0點也滿足動態(tài)著色的定義,其他點不影響,所以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動態(tài)著色,且v1,v2,v3,v4,v5在G1中上的色分別是1,2,3,4,5,考慮H1,3.

(1)若v1與v3分別居于2個連通分支中,在含v1的連通分支中交換1色和3色,由命題2知不影響動態(tài)著色,在G中把v0上1色即得G的用5種顏色的動態(tài)著色,所以d(v0)≤5.

(2)若v1與v3同在一個H1,3的連通分支中,則在G1中存在軌P(v1,v3),此軌道上的1色與3色交替出現(xiàn).考慮H2,4,若v2與v4分屬于2個連通分支中,與(1)相似,可得d(v0)≤5.而v2與v4不會出現(xiàn)在H2,4的同一個連通分支中,不然存在軌P(v2,v4),其上的頂2色與4色交替出現(xiàn),但在G中,有一個圈C0:v0v1P (v1,v3)v3v1.于是P(v1,v3)與P(v2,v4)必有公共頂點,這個公共頂點P(v1,v3)要求它是1色或者3色,而P(v2,v4)要求它是2色或者4色,這是不可能的.證畢.

3 結束語

動態(tài)著色是正常著色的一種“衍生物”,它有著廣泛的應用.幾類特殊圖和平面圖的動態(tài)著色的上界已經(jīng)研究清楚了,而一般圖的動態(tài)著色的上界到目前為止還沒有明確的結論,這也是動態(tài)著色問題的難點之一.

參考文獻:

[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] 秦健,張巖.單圈圖和雙圈圖的動態(tài)色數(shù)[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;通訊聯(lián)系人:趙克文(1964-),男,教授,主要從事圖論研究,E-mail:kewen.zhao@yahoo.com.cn.