林 越, 趙克文
(瓊州學(xué)院數(shù)學(xué)系 海南三亞572022)
平面圖的動態(tài)著色
林 越, 趙克文
(瓊州學(xué)院數(shù)學(xué)系 海南三亞572022)
研究平面圖的動態(tài)著色數(shù),通過定義一個算法得到強(qiáng)導(dǎo)出圖.利用顏色對換的思想來研究平面圖動態(tài)著色的上界問題,得到結(jié)論:若G是平面圖,則χd(G)≤5.
算法;強(qiáng)導(dǎo)出圖;動態(tài)著色
圖的著色理論在圖論中占有重要地位,其結(jié)論有著廣泛的應(yīng)用.關(guān)于圖G=(V,E),v∈V(G)的頂點(diǎn)度定義為圖G中與v關(guān)聯(lián)的邊的數(shù)目,記為dG(v),v的鄰域記為N(v).圖G的正常k頂點(diǎn)著色,簡稱圖的k頂點(diǎn)著色,用k種顏色對G的各頂點(diǎn)進(jìn)行著色,使得任意相鄰的2點(diǎn)著不同的顏色.若G至少有1個正常k頂點(diǎn)著色,就稱G是正常k點(diǎn)可著色的.使G是k點(diǎn)可著色的數(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).本文所研究的圖除特別說明外,均為簡單有限連通圖,文中沒給出的定義或術(shù)語可參考文獻(xiàn)[1].
文獻(xiàn)[2]首次提出了動態(tài)著色的概念;文獻(xiàn)[3]中討論了一些關(guān)于動態(tài)著色的性質(zhì),并證明一般圖的χd(G)≤Δ+3;文獻(xiàn)[4]研究了Pseudo-Halin圖的動態(tài)著色;文獻(xiàn)[5]研究了單圈圖和雙圈圖的動態(tài)色數(shù),并得到它們的動態(tài)色數(shù)是3或4;文獻(xiàn)[6]研究了沒有分支和C5同構(gòu)的圖的動態(tài)著色.本文主要討論平面圖動態(tài)著色的上界問題,得到定理1,即若G是平面圖,則χd(G)≤5.
在經(jīng)典“平面圖是5可頂點(diǎn)著色的”證明過程中,先找圖G的i色頂與j色頂?shù)膶?dǎo)出子圖Gi,j:i色與j色交替出現(xiàn)的一條軌道,然后對換該導(dǎo)出子圖的i色與j色,不影響圖G的正常著色.
把這一思想運(yùn)用到“平面圖是5可動態(tài)著色的”中來,首先找圖G的i色頂與j色頂強(qiáng)導(dǎo)出圖Hi,j:從任一著i色頂點(diǎn)v1開始,檢查其鄰域N(v1),若存在著j色的頂v2,那么把v1,v2看成Hi,j的2個頂點(diǎn),把v1, v2看成Hi,j的一條邊,接著繼續(xù)檢查v2的鄰域N(v2),重復(fù)下去,直到對于vk(vk著i色或者j色之一,不妨設(shè)vk著j色)來說,在其鄰域N(vk)中已經(jīng)不存在與其相鄰并且著i色頂點(diǎn),否則可以繼續(xù)重復(fù)下去,又因為本身著j色,當(dāng)然也不存與其相鄰并且著j色頂點(diǎn).這時檢查vk鄰域中的任一點(diǎn)vl,若滿足在NG(vl)-vk中任一頂點(diǎn)都著i色,連接其中著i色的一點(diǎn)vk+1,把vk+1并入Hi,j已有的頂點(diǎn)集,把vkvk+1并入Hi,j已有的邊集,然后又從vk+1開始檢查其鄰域,直到不能進(jìn)行下去為止.顯然,Hi,j也是i色與j色交替出現(xiàn)的一條軌道.
根據(jù)以上思想,給出強(qiáng)導(dǎo)出圖算法具體步驟如下:
若已存在=G(V,E)的一個頂點(diǎn)著色c,記c(i)={v|c(v)=i,v∈G}.
Step1設(shè)Hi,j=(V′,E′),V′=?,E′=?.
Step2設(shè)v0∈c(i),若不存在與其相鄰并且著j色的頂點(diǎn),轉(zhuǎn)Step3;若存在與其相鄰且著j色的頂點(diǎn)v1,V′∶=V′∪{v0,v1},E′∶=E′∪{v0v1},i∶=j,重復(fù)Step2直到不存在這樣的頂點(diǎn),結(jié)束.這時把最后一個并入V的頂點(diǎn)記為vk,vk著i色或者j色之一,不妨設(shè)vk著j色.
Step3若不存在頂點(diǎn)vl,滿足在NG(vl)-vk中任一頂點(diǎn)都著i色,結(jié)束.若存在這樣的頂點(diǎn)vl,V′∶= V′∪{v′l},E′∶=E′∪{vkv′l},其中v′l為NG(vl)-vk中著i色的任一頂點(diǎn).轉(zhuǎn)Step2.
通過以上作法得到的圖稱為i色頂和j色頂?shù)膹?qiáng)導(dǎo)出圖,記為Hi,j.在Step3中,選取的v′l為NG(vl)-vk中著i色的任一頂點(diǎn),那么很顯然Hi,j不唯一.
命題1如果圖G是平面圖,那么構(gòu)造Hi,j時添加的邊得到G′仍然是平面圖.
證明由構(gòu)造Hi,j的作法,所添加的邊是vkv′l,其中v′l為NG(vl)-vk中都著i色的任一頂點(diǎn),只需考慮添加的邊是否會破壞圖G的平面性即可.若存在NG(vl)-vk中的某一頂點(diǎn)與vk在同一個圈的內(nèi)部,那么添加邊vkv′l后,不破壞圖G的平面性.若NG(vl)-vk全都在有一個圈C內(nèi)部,而vk在這個圈的外部,可以斷定vl位于圈C上,所以必還有一頂v′l位于圈C上,又假設(shè)vk位于C的外部,所以添加邊vkv′l后也不會破壞圖G的平面性,G′=G+{vkv′l}仍然是平面圖.證畢.
命題2若已對平面圖G進(jìn)行動態(tài)著色,對換圖Hi,j中i,j兩種顏色不影響圖G的動態(tài)著色.
證明由Hi,j的作法,Hi,j是一i色與j色交替出現(xiàn)的子圖,且由Step3可知,交換后能保證每個頂點(diǎn)的鄰域至少能著2種顏色的動態(tài)著色性質(zhì)不變.證畢.
現(xiàn)在證明引言中提出的定理1.
證明設(shè)G是連通平面圖,對G的頂點(diǎn)數(shù)n進(jìn)行歸納證明.
當(dāng)n≤5時,定理顯然成立.假設(shè)n≤k-1時定理1已成立,只要證明n=k時定理也成立即可.
由于G是平面圖,δ≤5,設(shè)d(v0)≤5.
記G1=G-v0+xy,其中,x,y分別為N(v0)中的任意2個頂點(diǎn),若已存在這樣的一條邊則不再連接.
若d(v0)≤4,由歸納假設(shè)χd(G1)≤5,即G1中已用5種顏色動態(tài)著色,再把v0與它在G中的鄰域集(不超過4個)相異的顏色著色,可知,對于v0點(diǎn)也滿足動態(tài)著色的定義,其他點(diǎn)不影響,所以d(v0)≤5.
若d(v0)=5,設(shè)v1,v2,v3,v4,v5是v0的鄰頂點(diǎn),不妨設(shè)v1,v2,v3,v4,v5依順時針排列(不然重新對這5個頂點(diǎn)編號).由歸納假設(shè)χd(G1)≤5,設(shè)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)必有公共頂點(diǎn),這個公共頂點(diǎn)P(v1,v3)要求它是1色或者3色,而P(v2,v4)要求它是2色或者4色,這是不可能的.證畢.
動態(tài)著色是正常著色的一種“衍生物”,它有著廣泛的應(yīng)用.幾類特殊圖和平面圖的動態(tài)著色的上界已經(jīng)研究清楚了,而一般圖的動態(tài)著色的上界到目前為止還沒有明確的結(jié)論,這也是動態(tài)著色問題的難點(diǎn)之一.
參考文獻(xiàn):
[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].山東大學(xué)學(xué)報:理學(xué)版,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
海南省自然科學(xué)基金資助項目,編號10501.
林越(1981-),男,助教,碩士,主要從事圖論與算法研究,E-mail:linyue_306@163.com;通訊聯(lián)系人:趙克文(1964-),男,教授,主要從事圖論研究,E-mail:kewen.zhao@yahoo.com.cn.