張祥波

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

1 引言

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

圖的頂點(diǎn)染色是一個(gè)長期且困難的問題，對(duì)圖的結(jié)構(gòu)進(jìn)行正確合理地劃分，是研究頂點(diǎn)染色的關(guān)鍵。文獻(xiàn)[2-4]基于圖的結(jié)構(gòu)給出了一些特殊圖的頂點(diǎn)染色，文獻(xiàn)[5-7]從算法方面探討圖的頂點(diǎn)染色。從劃分圖的結(jié)構(gòu)出發(fā)，文獻(xiàn)[8]研究了一些特殊圖的頂點(diǎn)染色數(shù)，文獻(xiàn)[9-11]證明了以下結(jié)論。

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

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

定義1[8]如果圖G含有的所有最大團(tuán)存在公共頂點(diǎn)，且公共頂點(diǎn)的個(gè)數(shù)為k，則稱此圖為第k類圖。

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

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

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

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

證明設(shè)頂點(diǎn)u∈V′(GS),頂點(diǎn)v∈V(G-V′),u和v不相鄰。將頂點(diǎn)u和v刪掉，必得到一個(gè)頂點(diǎn)數(shù)是p-2且|S|=p-7的圖G′,由引理1知，χ(G′)≤p-6。添上頂點(diǎn)u和v，就得到原來的圖G，而色數(shù)最多增加1，故χ(G)≤p-5。

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

(1)V′(GS)中任意一個(gè)頂點(diǎn)與V(G-V′)中的所有頂點(diǎn)相鄰；

(2)圖G是第p-7類圖,

則χ(G)=p-6。

證明由于圖G是第p-7類圖，V′(GS)中任意一個(gè)頂點(diǎn)與V(G-V′)中的所有頂點(diǎn)相鄰，且|S|=p-6；則圖G-V′是頂點(diǎn)數(shù)為7的無邊圖。故χ(G-V′)=1。而圖GS有p-7個(gè)頂點(diǎn)，且是一個(gè)團(tuán)；故染p-7種顏色。因?yàn)閂′(GS)中任意一個(gè)頂點(diǎn)與V(G-V′)中的所有頂點(diǎn)相鄰，所以χ(G)=p-6。

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

(2)圖G是第p-8類圖,

則χ(G)≤p-5。

證明由圖G滿足的2個(gè)條件知，圖GS是頂點(diǎn)數(shù)為p-8的團(tuán),G-V′是頂點(diǎn)數(shù)為8且含最大團(tuán)K2的圖。于是0≤Δ(G-V′)≤7。0≤Δ(G-V′)≤2時(shí)，G-V′可分解成一些孤立點(diǎn)或路或圈等連通分支的并，易得χ(G-V′)≤3；Δ(G-V′)=k≥3時(shí)，設(shè)v0為k度點(diǎn)且v0與{v1,v2,…,vk}相鄰，則G-V′-{v0,v1,v2,…vk}中至多有8-(k+1)≤4個(gè)點(diǎn)，又不含K3，從而為二部圖，所以v0用顏色1染，{v1,v2,…,vk}中的點(diǎn)用顏色2染，其余點(diǎn)用顏色1和3染即可。從而χ(G-V′)≤3，結(jié)合(1)和(2)，故χ(G)≤p-5。

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

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

3 待解決的問題

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

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

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