一類特殊圖的頂點(diǎn)染色及其猜想的證明

張祥波(臨盤中學(xué)，山東臨邑251507)

一類特殊圖的頂點(diǎn)染色及其猜想的證明

張祥波
(臨盤中學(xué)，山東臨邑251507)

通過研究一類特殊圖的頂點(diǎn)染色，得到了以下結(jié)果:給出了且p∈{4，5，6}，圖G的頂點(diǎn)染色數(shù);證明了的圖G不存在第p－m類圖，m≥7且m是正整數(shù);證明了時(shí)，χ(G)≤4θ(G)+θ2(G)－1;進(jìn)一步證明了猜想χ(G)≤4θ(G)+θ2(G)－1是正確的;為今后研究該猜想和圖的頂點(diǎn)染色提供一些思想方法.

頂點(diǎn)染色;最大團(tuán);第k類圖;圖的厚度

1　基礎(chǔ)知識(shí)

文中有關(guān)的概念和符號(hào)參見文獻(xiàn)［1，2］.V(G)，E(G)，θ(G)，χ(G)分別是圖G的頂點(diǎn)集、邊集、厚度、頂點(diǎn)染色數(shù).設(shè)S是圖G的一個(gè)團(tuán)，由于圖G必有最大團(tuán)，用表示圖G最大團(tuán)的頂點(diǎn)數(shù).如果圖G含有的所有最大團(tuán)存在公共頂點(diǎn)，且公共頂點(diǎn)的個(gè)數(shù)為k，則稱此圖為第k類圖［1］.圖G含有的所有最大團(tuán)的公共頂點(diǎn)及它們?cè)趫DG中的邊構(gòu)成的子圖，記作圖Gs(V'，E')，簡(jiǎn)稱圖Gs.V'(Gs)是圖G含有的所有最大團(tuán)的公共頂點(diǎn)集.G－V'表示從G中刪去V'(Gs)的所有頂點(diǎn)及其與V'(Gs)中頂點(diǎn)關(guān)聯(lián)的一切邊后得到的圖.

一般圖的頂點(diǎn)染色是非常復(fù)雜的，目前較多地是研究特殊圖的頂點(diǎn)染色［3－7］.為研究一般圖的頂點(diǎn)染色，文獻(xiàn)［8］提出了圖的色數(shù)與厚度的猜想:χ(G)≤4θ(G)+θ2(G)－1.文獻(xiàn)［9］定理3—5分別證明了完全圖、時(shí)，猜想是成立的;文末提出了有待研究的2個(gè)問題:

問題1［9］時(shí)，χ(G)≤4θ(G)+θ2(G)－1是否成立?

問題2［9］若則χ(G)=p－3或p－2，那么滿足什么條件的圖，χ(G)=p－3;滿足什么條件的圖，χ(G)=p－2.

文獻(xiàn)［1］通過研究問題2，提出了研究圖的頂點(diǎn)染色的一種新方法，并利用該方法得到了該問題在時(shí)，圖的4種頂點(diǎn)染色.

引理1［1］的圖G，若圖Gs中存在一個(gè)頂點(diǎn)與圖G－V'的頂點(diǎn)中至少一個(gè)不相鄰，則χ(G)=p－3.

引理2［1］的圖G，若只含有一個(gè)最大團(tuán)Kp－3，則χ(G)=p－3.

引理3［1］如果的圖G滿足下列條件:

1)V'(Gs)中任意一個(gè)頂點(diǎn)與V(G－V')中的所有頂點(diǎn)相鄰;

2)圖G是第p－4類圖或第p－6類圖.

則χ(G)=p－3.

引理4［1］圖G滿足下列條件:

1)V'(Gs)中任意一個(gè)頂點(diǎn)與V(G－V')中的所有頂點(diǎn)相鄰;

2)圖G是第p－5類圖.

若圖G－V'中不存在奇圈，則χ(G)=p－3;若圖G－V'中存在奇圈，則χ(G)=p－2.

但問題2尚未完全解決，文獻(xiàn)［1］在文末將其未解決的部分總結(jié)為第5個(gè)問題.此處的研究是給出p－3且p∈{4，5，6}，圖的各種頂點(diǎn)染色;證明時(shí)，圖G不存在第p－m類圖，m≥7且m是正整數(shù).進(jìn)一步證明文獻(xiàn)［9］提出的問題1是成立的.綜合上述4個(gè)引理，從而完全解決文獻(xiàn)［9］提出的第2個(gè)問題.

①p=4時(shí)，S=1，則χ(G)=1;

②p=5時(shí)，圖G含最大團(tuán)K2，若不存在奇圈，則χ(G)=2;若存在奇圈，則χ(G)=3.

證明圖G若存在奇圈，由于含最大團(tuán)K2，所以奇圈必是5－圈，于是χ(G)=3.

其次考慮圖G不存在奇圈的情況，若所有最大團(tuán)K2有公共頂點(diǎn)，則只有一個(gè)公共頂點(diǎn)，于是必有χ(G)=2;若所有最大團(tuán)K2不存在公共頂點(diǎn)，由文獻(xiàn)［1］定理4的證明可知χ(G)=2.

引理5［9］若，則χ(G)=p－2.

①若該公共頂點(diǎn)與圖G－V'中的一個(gè)頂點(diǎn)不相鄰，則χ(G)=3;

②若該公共頂點(diǎn)與圖G－V'中的所有頂點(diǎn)相鄰，且圖G－V'存在奇圈，則χ(G)=4;

③若該公共頂點(diǎn)與圖G－V'中的所有頂點(diǎn)相鄰，且圖G－V'不存在奇圈，則χ(G)=3.

證明先證①，設(shè)u是圖G所有最大團(tuán)K3的公共頂點(diǎn)，v是圖G－V'的一個(gè)頂點(diǎn)，u和v不相鄰，將u和v刪掉，必得到一個(gè)頂點(diǎn)數(shù)是4，含最大團(tuán)K2的圖G1.由引理5知，χ(G1)=2，添上頂點(diǎn)u和v，則圖G的色數(shù)增加1，故χ(G)=3.

關(guān)于②，設(shè)u是所有最大團(tuán)K3的公共頂點(diǎn)，則G－V'是一個(gè)頂點(diǎn)數(shù)是5，含最大團(tuán)K2的圖.由于圖G－V'存在奇圈，則必是一個(gè)5－圈，所以χ(G－V')=3，由于u與圖G－V'的所有頂點(diǎn)相鄰，故χ(G)=4.

關(guān)于③，由條件知，圖G－V'是一個(gè)頂點(diǎn)數(shù)是5，含最大團(tuán)K2的圖.由于圖G－V'不存在奇圈，所以由文獻(xiàn)［1］定理4的證明可知，χ(G)=3.

證明分兩種情況.

情況1有一個(gè)公共頂點(diǎn)與圖G－V'中的一個(gè)頂點(diǎn)不相鄰.設(shè)u是圖G所有最大團(tuán)K3的公共頂點(diǎn)，v是圖G－V'的一個(gè)頂點(diǎn)，u和v不相鄰，將u和v刪掉，必得到一個(gè)頂點(diǎn)數(shù)是4，含最大團(tuán)K2的圖G1.由引理5知，χ (G1)=2，添上頂點(diǎn)u和v，則圖G的色數(shù)增加1，故χ(G)=3.

情況2 2個(gè)公共頂點(diǎn)與圖G－V'的所有頂點(diǎn)相鄰，則圖G－V'中所有頂點(diǎn)互不相鄰，于是χ(G－V')=1，故χ(G)=3.

由文獻(xiàn)［1］定理3的證明可知該定理成立，此處證明略.

3　關(guān)于第p－m類圖

引理6［9］若，則圖G含有的所有最大團(tuán)必存在公共頂點(diǎn).

證明使用反證法證明.

假設(shè)圖G是第p－m類圖，則圖G中所有最大團(tuán)Kp－3有p－m個(gè)公共頂點(diǎn).考慮其中一個(gè)最大團(tuán)S1，則必有3個(gè)頂點(diǎn)不是S1的頂點(diǎn).不妨設(shè)這3個(gè)頂點(diǎn)分別是u1，u2，u3，于是u1，u2，u3中至少有一個(gè)頂點(diǎn)在除S1外的最大團(tuán)Kp－3中.考慮3種情況:

情況1若u1，u2，u3都是最大團(tuán)Kp－3(除S1外)的頂點(diǎn)，則圖Gs與圖G－V'所有頂點(diǎn)相鄰.于是將圖Gs的所有頂點(diǎn)都刪去，必得到一個(gè)頂點(diǎn)數(shù)是m，含有最大團(tuán)的頂點(diǎn)數(shù)是m－3的圖G1.由于m≥7，故由引理6知，圖G1中所有最大團(tuán)Km－3必有公共頂點(diǎn).從而圖G中所有最大團(tuán)Kp－3的公共頂點(diǎn)數(shù)大于p－m，這與圖G中所有最大團(tuán)Kp－3有p－m個(gè)公共頂點(diǎn)矛盾.

情況2u1，u2，u3中只有一個(gè)頂點(diǎn)是最大團(tuán)Kp－3的頂點(diǎn).不妨設(shè)u1是最大團(tuán)Kp－3的頂點(diǎn)，則u2和u3不是最大團(tuán)Kp－3的頂點(diǎn).于是將圖Gs及u2，u3都刪掉，必得到頂點(diǎn)數(shù)是m－2，含最大團(tuán)Km－3的圖G'.由于m≥7，故由引理6知，圖G'中所有最大團(tuán)K必有公共頂點(diǎn).從而圖G中所有最大團(tuán)K的公共頂點(diǎn)數(shù)

m－3p－3大于p－m，這與圖G中所有最大團(tuán)Kp－3有p－m個(gè)公共頂點(diǎn)矛盾.

情況3u1，u2，u3中只有2個(gè)頂點(diǎn)是最大團(tuán)Kp－3的頂點(diǎn).不妨設(shè)u1和u2是最大團(tuán)Kp－3的頂點(diǎn)，則u3不是最大團(tuán)Kp－3的頂點(diǎn).將圖Gs和u3都刪掉，必得到一個(gè)頂點(diǎn)數(shù)是m－1，含最大團(tuán)Km－3的圖G2.由于m≥7，故.由引理6知，圖G2中所有最大團(tuán)Km－3必有公共頂點(diǎn).從而圖G中所有最大團(tuán)Kp－3的公共頂點(diǎn)數(shù)大于p－m，這與圖G中所有最大團(tuán)Kp－3有p－m個(gè)公共頂點(diǎn)矛盾.

綜合以上3種情況，假設(shè)不成立，定理得證.

引理7［9］若，則χ(G)≤p－2.

引理8［10］，其中Kn是完全圖.

證明由前面的結(jié)論易知，p=4時(shí)，χ(G)=1;p=5時(shí)，χ(G)=2或3;p=6時(shí)，由定理1，定理2，定理3，定理4知，χ(G)=3或4，而4θ(G)+θ2(G)－1≥4.故且p∈{4，5，6}時(shí)，χ(G)≤4θ(G)+θ2(G)－1.

②p=6k－1，6k－2，6k－3，6k－4時(shí)，同理可證，均有χ(G)≤4θ(G)+θ2(G)－1.

綜上各種情況得證，S =p－3時(shí)，有χ(G)≤4θ(G)+θ2(G)－1.

5　結(jié)束語

在文獻(xiàn)［1］的基礎(chǔ)上，解決了文獻(xiàn)［1］在文末提出的第5個(gè)問題，結(jié)合文獻(xiàn)［1］已經(jīng)得到的4個(gè)定理，從而完全解決了文獻(xiàn)［9］提出的問題2.這為研究時(shí)，圖的頂點(diǎn)染色，提供了一些思想和方法.文末利用這些結(jié)論，證明了文獻(xiàn)［9］提出的問題1是正確的.因此，有理由猜測(cè)時(shí)，該猜想是否成立.至此，文獻(xiàn)［9］提出的2個(gè)問題已全部解決;同時(shí)文獻(xiàn)［1］提出的5個(gè)有待研究的問題中，還有3個(gè)尚待研究.另外注意到證明的定理4，由此猜想的圖G，是否存在第p－q類圖，q≥2m+1，m≥3且m是正整數(shù).此外定理4證明了m=3的情況是不存在的，對(duì)于m≥4的情況還有待研究.

［1］張祥波.一類特殊圖的頂點(diǎn)染色數(shù)［J］.安慶師范學(xué)院學(xué)報(bào):自然科學(xué)版，2015，21(3):130-135

［2］謝政，戴麗.組合圖論［M］.長(zhǎng)沙:國(guó)防科技大學(xué)出版社，2003

［3］劉廣德，雙外平面圖的點(diǎn)染色［J］.棗莊學(xué)院學(xué)報(bào)，2013，30(5):63-65

［4］亢瑩利，王應(yīng)前.平面圖3色可染的一個(gè)充分條件［J］.中國(guó)科學(xué):數(shù)學(xué)，2013，43(4):409-421

［5］彩春麗，謝德政.平面圖3－可著色的3個(gè)充分條件［J］.河南師范大學(xué)學(xué)報(bào):自然科學(xué)版，2011，39(6):4-6;28

［6］劉配配，王應(yīng)前.不含4－圈與7－圈的平面圖是(2，0，0)－可染的［J］.中國(guó)科學(xué):數(shù)學(xué)，2014，44(11):1153-1164

［7］胡鳳鳳，劉家保.關(guān)于一類圖的鄰點(diǎn)可區(qū)別全染色［J］.重慶工商大學(xué)學(xué)報(bào):自然科學(xué)版，2015，32(2):23-26

［8］張祥波.研究四色問題的意義及理論構(gòu)想［J］.數(shù)學(xué)理論與應(yīng)用，2012，32(3):24-28

［9］張祥波，魏志芹.關(guān)于圖的色數(shù)與厚度的一些新結(jié)果［J］.高師理科學(xué)刊，2013，33(5):35-37

［10］卜月華.圖論及其應(yīng)用［M］.南京:東南大學(xué)出版社，2002

(1)Give vertex coloring number of graph G=p－3and p∈{4，5，6}.

(2)Prove that graph G ofhas no the p－m class of graph，m≥7and m is positive integer.

(3)Prove thatχ(G)≤4θ(G)+θ2(G)－1，when

All kinds of vertex coloring number of graph G whenare given from these results above，and further it is proven that the conjectureχ(G)≤4θ(G)+θ2(G)－1 is right.，which provide some thoughts and methods for further study on this conjecture and the graph vertex coloring.

Proof of a Conjecture of A Class of Vertex Coloring of Special Graphs

ZHANG Xiang-bo
(Linpan Middle School，Linyi 251507，China)

Throughout the study on a class of vertex coloring of special graphs，this paper gives the following results:

vertex coloring，themaximum clique，thekclass of graph，thickness of a graph

O157.5

A

1672－058X(2015)09－0066－05

10.16055/j.issn.1672－058X.2015.0009.017

2015－01－23;

2015－03－11.

張祥波(1978-)，山東臨邑人，中教一級(jí)，從事圖的染色研究.