張祥波
(德州市臨邑縣臨盤中學,山東 德州 251507)
有關(guān)的術(shù)語和記號參見文獻[1]。用G表示一個簡單有限無向圖,設χ(G)、|S|、Δ(G)分別表示圖G的頂點染色數(shù)、最大團的頂點數(shù)、最大度,|V(G)|表示圖G的頂點數(shù),記作p=|V(G)|。圖G中含有的所有最大團K|S|的公共頂點及其在圖G中的邊構(gòu)成的子圖,記作圖GS(V′,E′),簡稱圖GS。V′,E′分別是圖GS的頂點集和邊集。用G-V′表示從G中刪去V′(GS)的所有頂點及其與V′(GS)中頂點關(guān)聯(lián)的一切邊后得到的圖。
圖的頂點染色是一個長期且困難的問題,對圖的結(jié)構(gòu)進行正確合理地劃分,是研究頂點染色的關(guān)鍵。文獻[2-4]基于圖的結(jié)構(gòu)給出了一些特殊圖的頂點染色,文獻[5-7]從算法方面探討圖的頂點染色。從劃分圖的結(jié)構(gòu)出發(fā),文獻[8]研究了一些特殊圖的頂點染色數(shù),文獻[9-11]證明了以下結(jié)論。
定理若|S|∈{p,p-1,p-2,p-3,p-4,p-5},則χ(G)≤|S|+1。
本文繼續(xù)探討這個結(jié)論,提出一個新的猜想:χ(G)≤|S|+C,C∈Z+且C為常數(shù)。若C=1,我們證明對于|S|=p-6的一些圖,有χ(G)≤p-5。
定義1[8]如果圖G含有的所有最大團存在公共頂點,且公共頂點的個數(shù)為k,則稱此圖為第k類圖。
引理1[11]若|S|=p-5,則χ(G)≤p-4。
引理2[2]圖G是二部圖,當且僅當G中不含奇圈。
引理3[9]若|S|=p-2,則χ(G)=p-2。
證明設頂點u∈V′(GS),頂點v∈V(G-V′),u和v不相鄰。將頂點u和v刪掉,必得到一個頂點數(shù)是p-2且|S|=p-7的圖G′,由引理1知,χ(G′)≤p-6。添上頂點u和v,就得到原來的圖G,而色數(shù)最多增加1,故χ(G)≤p-5。
由定理1的證明知推論成立。
(1)V′(GS)中任意一個頂點與V(G-V′)中的所有頂點相鄰;
(2)圖G是第p-7類圖,
則χ(G)=p-6。
證明由于圖G是第p-7類圖,V′(GS)中任意一個頂點與V(G-V′)中的所有頂點相鄰,且|S|=p-6;則圖G-V′是頂點數(shù)為7的無邊圖。故χ(G-V′)=1。而圖GS有p-7個頂點,且是一個團;故染p-7種顏色。因為V′(GS)中任意一個頂點與V(G-V′)中的所有頂點相鄰,所以χ(G)=p-6。
(1)V′(GS)中任意一個頂點與V(G-V′)中的所有頂點相鄰,
(2)圖G是第p-8類圖,
則χ(G)≤p-5。
證明由圖G滿足的2個條件知,圖GS是頂點數(shù)為p-8的團,G-V′是頂點數(shù)為8且含最大團K2的圖。于是0≤Δ(G-V′)≤7。0≤Δ(G-V′)≤2時,G-V′可分解成一些孤立點或路或圈等連通分支的并,易得χ(G-V′)≤3;Δ(G-V′)=k≥3時,設v0為k度點且v0與{v1,v2,…,vk}相鄰,則G-V′-{v0,v1,v2,…vk}中至多有8-(k+1)≤4個點,又不含K3,從而為二部圖,所以v0用顏色1染,{v1,v2,…,vk}中的點用顏色2染,其余點用顏色1和3染即可。從而χ(G-V′)≤3,結(jié)合(1)和(2),故χ(G)≤p-5。
推論2p=8且含最大團K2的圖G,則χ(G)≤3。
由定理3的證明知推論2成立。
(1)V′(GS)中任意一個頂點與V(G-V′)中的所有頂點相鄰,
(2)圖G是第p-k類圖(k=9,10,11,12),
則是否有χ(G)≤|S|+1?