關于頂點染色的一個猜想

張祥波

(德州市臨邑縣臨盤中學，山東 德州 251507)

1 引言

有關的術語和記號參見文獻[1]。用G表示一個簡單有限無向圖，設χ(G)、|S|、Δ(G)分別表示圖G的頂點染色數、最大團的頂點數、最大度，|V(G)|表示圖G的頂點數，記作p=|V(G)|。圖G中含有的所有最大團K|S|的公共頂點及其在圖G中的邊構成的子圖，記作圖GS(V′,E′),簡稱圖GS。V′，E′分別是圖GS的頂點集和邊集。用G-V′表示從G中刪去V′(GS)的所有頂點及其與V′(GS)中頂點關聯的一切邊后得到的圖。

圖的頂點染色是一個長期且困難的問題，對圖的結構進行正確合理地劃分，是研究頂點染色的關鍵。文獻[2-4]基于圖的結構給出了一些特殊圖的頂點染色，文獻[5-7]從算法方面探討圖的頂點染色。從劃分圖的結構出發，文獻[8]研究了一些特殊圖的頂點染色數，文獻[9-11]證明了以下結論。

定理若|S|∈{p,p-1,p-2,p-3,p-4,p-5}，則χ(G)≤|S|+1。

本文繼續探討這個結論，提出一個新的猜想：χ(G)≤|S|+C，C∈Z+且C為常數。若C=1，我們證明對于|S|=p-6的一些圖，有χ(G)≤p-5。

定義1[8]如果圖G含有的所有最大團存在公共頂點，且公共頂點的個數為k，則稱此圖為第k類圖。

引理1[11]若|S|=p-5,則χ(G)≤p-4。

引理2[2]圖G是二部圖，當且僅當G中不含奇圈。

引理3[9]若|S|=p-2,則χ(G)=p-2。

2 |S|=p-6的一些圖

證明設頂點u∈V′(GS),頂點v∈V(G-V′),u和v不相鄰。將頂點u和v刪掉，必得到一個頂點數是p-2且|S|=p-7的圖G′,由引理1知，χ(G′)≤p-6。添上頂點u和v，就得到原來的圖G，而色數最多增加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′是頂點數為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是頂點數為p-8的團,G-V′是頂點數為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，結合(1)和(2)，故χ(G)≤p-5。

推論2p=8且含最大團K2的圖G,則χ(G)≤3。

由定理3的證明知推論2成立。

3 待解決的問題

(1)V′(GS)中任意一個頂點與V(G-V′)中的所有頂點相鄰,

(2)圖G是第p-k類圖(k=9,10,11,12),

則是否有χ(G)≤|S|+1？