一類特殊圖的頂點染色數

張 祥 波

(臨盤中學，　山東　臨邑　251507)

?

一類特殊圖的頂點染色數

張 祥 波

(臨盤中學，山東臨邑251507)

摘要：如果圖G含有的所有最大團存在公共頂點，且公共頂點的個數為k，就稱此圖為第k類圖。據此，本文給出了研究圖的頂點染色的一種新方法，并以此研究了一類特殊圖的頂點染色及一些圖的頂點染色數。

關鍵詞：最大團；頂點染色數；第k類圖；圖的厚度

1預備知識

關于文中所用術語和簡稱，以下不加說明地沿用文獻[19]。文中僅考慮無向簡單圖，V(G)是圖G的頂點集，|V(G)|是圖G的頂點數，記作p=|V(G)|，E(G)是圖G的邊集，χ(G)是圖G的頂點染色數。設S是圖G的頂點集V(G)的子集，若S的生成子圖G[S]是完全圖，則稱S是圖G的一個團。顯然，圖G必存在最大團，用|S|表示圖G最大團的頂點數。圖G含有的所有最大團K|S|的公共頂點及它們在圖G中的邊構成的子圖，記作圖GS(V′,E′)，簡稱圖GS。其中V′(GS)是V(G)的非空子集，E′(GS)是E(G)的非空子集。顯然V′(GS)是圖G含有的所有最大團K|S|的公共頂點集。G-V′表示從G中刪去V′(GS)的所有頂點及其與V′(GS)中頂點關聯的一切邊后得到的圖。

定義1若圖G含有的所有最大團存在公共頂點，公共頂點的個數為k，則稱其為第k類圖。

引理2[20]若|S|=p-2，則χ(G)=p-2。

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

2主要結果

證明設頂點u∈V′(GS)，頂點v∈V(G-V′)，u和v不相鄰。將頂點u和v刪掉，必得到一個頂點數是p-2且|S|=p-4的圖G′，由引理2知， χ(G′)=p-4。添上頂點u和v，就得到原來的圖G，所以圖G的色數必增加1，即χ(G)=p-3。

證明由圖G只含有一個最大團Kp-3，故V′(GS)與V(G-V′)中必有一個頂點不相鄰，否則與|S|=p-3矛盾。由定理1， χ(G)=p-3。

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

(2)圖G是第p-4類圖或第p-6類圖，則χ(G)=p-3。

證明若圖G是第p-4類圖，V′(GS)中任意一個頂點與V(G-V′)中的所有頂點相鄰，且|S|=p-3，則V(G-V′)中的所有頂點互不相鄰。于是V(G-V′)中的所有頂點必染同一種顏色,而V′(GS)有p-4個頂點，且是一個團,故必染p-4種顏色。因為V′(GS)中任意一個頂點和V(G-V′)中的所有頂點相鄰，所以χ(G)=p-3。

若圖G是第p-6類圖，則圖G的所有最大團Kp-3有p-6個公共頂點。因此G-V′有6個頂點，含最大團K3的圖。但圖G-V′中所有最大團K3沒有公共頂點，否則與圖G是第p-6類圖矛盾。因此圖G-V′中的所有最大團K3有以下4種情況。

(1)任意2個最大團K3不存在公共頂點，則圖G-V′中只有2個最大團K3。不妨設最大團分別是S1和S2，則S1和S2中至少有一對頂點不相鄰。將這對不相鄰的頂點刪掉，必得到一個頂點數是4，含有最大團K2的圖G1。

由引理2知， χ(G1)=2，將刪掉的頂點添上，就得到原來的圖G-V′，所以頂點染色數必增加1，故χ(G-V′)=3。但V′(GS)中的任意一個頂點與V(G-V′)中的所有頂點相鄰，且GS是一個頂點數p-6是的完全圖，所以 χ(G)=p-3。

(2)存在2個最大團K3只有一個公共頂點，設最大團S1和S2只有一個公共頂點u，則圖G-V′中必存在一個最大團S3，使u一定不是S3的頂點，否則造成所有的最大團K3有公共頂點。下面考慮由最大團S1和S2構成的含有最大團K3，頂點數是5的G1圖。設圖G-V′的另外一個頂點是v，v?V(G1)，則v必是最大團S3的一個頂點，所以S3的另外2個頂點屬于V(G1)。由于頂點u與圖G1中的其余4個頂點相鄰，所以u與v一定不相鄰。將u和v刪掉，必得到頂點數是4，含最大團K2的圖，由引理2知，該圖的色數是2。添上u和v，則頂點染色數必增加1，故χ(G-V′)=3， χ(G)=p-3。

(3)任意2個最大團K3有2個公共頂點，下面證明該情況不存在。設最大團S1的頂點是v1，v2，v3，最大團S2的頂點是v1，v2，v4，于是S1和S2構成一個頂點數是4，含最大團K3的圖。設圖G-V′的另外2個頂點是v5和v6，所以不存在以v5和v6為頂點的最大團K3，否則與S1和S2只有一個公共頂點，矛盾。而圖G-V′中必存在以v5或v6為頂點的最大團K3，否則圖G-V′中只含有最大團S1和S2，這就造成圖G-V′中所有最大團K3有公共頂點，矛盾。而事實上，只要存在以v5或v6為頂點的最大團K3，則v5或v6必定與v1和v2相鄰(否則存在2個最大團K3只有一個公共頂點，這與所給的情況不符)。這就造成了圖G-V′中所有最大團K3存在公共頂點，這與圖G-V′中所有最大團K3不存在公共頂點矛盾。故上述情況是不存在的。

(4)任意2個最大團K3或有2個公共頂點或沒有公共頂點。下面證明該情況是不存在的。設最大團S1的頂點v1，v2，v3，最大團S2的頂點v4，v5，v6，則S1和S2無公共頂點。由圖G-V′是頂點數為6的圖，圖G-V′中其余的任意一個最大團K3，則只能同時與S1和S2有兩個公共頂點，矛盾。故該情況是不存在的。

綜上各種情況證明，從而定理得證。

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

(2)圖G是第p-5類圖；

若圖G-V′中不存在奇圈，則χ(G)=p-3；若圖G-V′中存在奇圈，則χ(G)=p-2。

證明由圖G是第p-5類圖，|S|=p-3，則G-V′是一個頂點數為5，且含有最大團K2的圖。下面分兩種情況給出圖G-V′的頂點染色數。由引理3知，χ(G-V′)=2或χ(G-V′)=3。

情況1圖G-V′中不存在奇圈。圖G-V′中有2個最大團K2不存在公共頂點。設v1，v2，v3，v4，v5是圖G-V′中的5個頂點，其中v1與v2，v3與v4分別是2個最大團K2的頂點，故v1與v2相鄰，v3與v4相鄰，而v5最多與v1，v2或v3，v4中的一個相鄰。若v5是孤立點，則有χ(G-V′)=2；若v5與v1，v2中的一個相鄰，同時與v3，v4中的一個相鄰，不妨設v5與v1相鄰，v5與v3相鄰，則v1與v3不相鄰，從而v2與v4一定不相鄰，否則圖G-V′中存在奇圈。另設v1染顏色1，v2染顏色2，于是v3染顏色1，v4染顏色2，而v5染顏色2，故χ(G-V′)=2。由于是第p-5類圖，故圖GS是一個頂點數是p-5的完全圖，而且圖G還滿足條件(1)，故χ(G)=p-3。

情況2圖G-V′中存在奇圈。由圖G-V′的頂點是5，則圖G-V′中存在5-圈，必有χ(G-V′)=3，進而χ(G)=p-2。

綜合以上情況，定理得證。

3進一步解決的問題

參考文獻:

[1] 林妍, 吳瑾, 樊鎖海. 圖著色和標號問題的蟻群優化算法[J]. 數學的實踐與認識, 2012, 42(17): 182-191.

[2] T.R.Jensen, B.Toft. Graph coloring problems[M]. New York: Wiley-Interscience, 1995.

[3] E.Malaguti, P.Toth. A survey on vertex coloring problems[J]. International Transactions in Operational Research, 2010, 17(1): 1-34.

[4] E.Salari, K.Eshghi. An ACO algorithm for the graph coloring problem[J].Int. J. Contemp. Math. Sciences, 2008, 3(6): 293-304.

[5] 朱虎, 宋恩民, 路志宏. 求解圖著色問題的最大最小蟻群搜索算法[J]. 計算機仿真, 2010, 27(3): 190-192, 236.

[6] 安常勝, 馮旭霞. 幾類特殊圖的補倍圖的點色數[J]. 天水師范學院學報, 2008, 28(2): 8-9.

[7] 謝繼國, 張效賢, 徐剛. 一類6-正則循環圖的點色數[J]. 甘肅高師學報, 2007, 12(5): 1-3.

[8] 達文姣, 任志國. 扇、輪和完全圖的r(2)點色數[J]. 甘肅聯合大學學報(自然科學版),2011, 25(2): 11-12.

[9] 任志國, 趙傳成, 張忠輔, 等. 關于Sm∨Fn的邊色數和點色數[J]. 蘭州交通大學學報(自然科學版),2006, 25(4): 147-149.

[10]張忠輔, 王建方, 李正良. 關于圖的3-色數[J]. 電子科技大學學報, 1991, 20(1): 88-91.

[11] Xu Kexiang, Song Zengmin. Coloring of some integer distance graphs[J]. Journal of Southeast University(English Edition), 2003, 19(4): 418-422.

[12] 徐靈姬, 王應前. 既不含4-圈又不含6-圈的平面圖的非正常染色[J]. 中國科學: 數學, 2013, 43(1): 15-24.

[13] 卜月華, 朱旭波. 不含短圈的平面圖的2-距離染色[J]. 中國科學: 數學, 2012, 42(6): 635-644.

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

[15] 王維凡, 陳敏. 不含4，6，8-圈的平面圖是3-可染的[J]. 中國科學A輯, 2007, 37(8): 982-992.

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

[17] 許洋, 張雪媛. 關于平面圖的3-可染色的一些結果[J]. 青島農業大學學報(自然科學版), 2011, 28(1): 75-78.

[18] 任玉杰. 不含k3的平面圖最多是-4可著色的[J]. 大學數學, 2004, 20(2): 87-88.

[19] 謝政, 戴麗. 組合圖論[M]. 長沙:國防科技大學出版社, 2003: 4-5, 59.

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

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

A Class Vertex Coloring Number of Special Graphs

ZHANG Xiang-bo

(Linpan School, Linyi 251507, China)

Abstract:If there are common vertexes in all the maximum cliques of graph, and there are k common vertexes, then we call graph is the k class graph. Hereby, this paper gives a new method to study vertex coloring of graph. According to this method, this paper studies a class vertex coloring of special graphs, and gives vertex coloring number of some graphs.

Key words:the maximum clique, vertex coloring number, first k class of graph, thickness of a graph

文章編號：1007-4260(2015)03-0011-03

中圖分類號：O157.5

文獻標識碼：A

DOI：10.13757/j.cnki.cn34-1150/n.2015.03.004

作者簡介：張祥波，男，山東臨邑人，臨盤中學一級教師，研究方向為圖的染色。

收稿日期：2014-09-25

網絡出版時間：2015-8-25 15:40網絡出版地址：http://www.cnki.net/kcms/detail/34.1150.N.20150825.1540.004.html