一類特殊圖的頂點染色及其猜想的證明

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

一類特殊圖的頂點染色及其猜想的證明

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

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

頂點染色;最大團;第k類圖;圖的厚度

1　基礎知識

文中有關的概念和符號參見文獻［1，2］.V(G)，E(G)，θ(G)，χ(G)分別是圖G的頂點集、邊集、厚度、頂點染色數.設S是圖G的一個團，由于圖G必有最大團，用表示圖G最大團的頂點數.如果圖G含有的所有最大團存在公共頂點，且公共頂點的個數為k，則稱此圖為第k類圖［1］.圖G含有的所有最大團的公共頂點及它們在圖G中的邊構成的子圖，記作圖Gs(V'，E')，簡稱圖Gs.V'(Gs)是圖G含有的所有最大團的公共頂點集.G－V'表示從G中刪去V'(Gs)的所有頂點及其與V'(Gs)中頂點關聯的一切邊后得到的圖.

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

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

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

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

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

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

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

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

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

則χ(G)=p－3.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

關于③，由條件知，圖G－V'是一個頂點數是5，含最大團K2的圖.由于圖G－V'不存在奇圈，所以由文獻［1］定理4的證明可知，χ(G)=3.

證明分兩種情況.

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

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

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

3　關于第p－m類圖

引理6［9］若，則圖G含有的所有最大團必存在公共頂點.

證明使用反證法證明.

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

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

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

m－3p－3大于p－m，這與圖G中所有最大團Kp－3有p－m個公共頂點矛盾.

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

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

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

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

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

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

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

5　結束語

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

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

［2］謝政，戴麗.組合圖論［M］.長沙:國防科技大學出版社，2003

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

［4］亢瑩利，王應前.平面圖3色可染的一個充分條件［J］.中國科學:數學，2013，43(4):409-421

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

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

［7］胡鳳鳳，劉家保.關于一類圖的鄰點可區別全染色［J］.重慶工商大學學報:自然科學版，2015，32(2):23-26

［8］張祥波.研究四色問題的意義及理論構想［J］.數學理論與應用，2012，32(3):24-28

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

［10］卜月華.圖論及其應用［M］.南京:東南大學出版社，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-)，山東臨邑人，中教一級，從事圖的染色研究.