張 祥 波

(臨盤(pán)中學(xué)，　山東　臨邑　251507)

?

一類(lèi)特殊圖的頂點(diǎn)染色數(shù)

張 祥 波

(臨盤(pán)中學(xué)，山東臨邑251507)

摘要：如果圖G含有的所有最大團(tuán)存在公共頂點(diǎn)，且公共頂點(diǎn)的個(gè)數(shù)為k，就稱(chēng)此圖為第k類(lèi)圖。據(jù)此，本文給出了研究圖的頂點(diǎn)染色的一種新方法，并以此研究了一類(lèi)特殊圖的頂點(diǎn)染色及一些圖的頂點(diǎn)染色數(shù)。

關(guān)鍵詞：最大團(tuán)；頂點(diǎn)染色數(shù)；第k類(lèi)圖；圖的厚度

1預(yù)備知識(shí)

關(guān)于文中所用術(shù)語(yǔ)和簡(jiǎn)稱(chēng)，以下不加說(shuō)明地沿用文獻(xiàn)[19]。文中僅考慮無(wú)向簡(jiǎn)單圖，V(G)是圖G的頂點(diǎn)集，|V(G)|是圖G的頂點(diǎn)數(shù)，記作p=|V(G)|，E(G)是圖G的邊集，χ(G)是圖G的頂點(diǎn)染色數(shù)。設(shè)S是圖G的頂點(diǎn)集V(G)的子集，若S的生成子圖G[S]是完全圖，則稱(chēng)S是圖G的一個(gè)團(tuán)。顯然，圖G必存在最大團(tuán)，用|S|表示圖G最大團(tuán)的頂點(diǎn)數(shù)。圖G含有的所有最大團(tuán)K|S|的公共頂點(diǎn)及它們?cè)趫DG中的邊構(gòu)成的子圖，記作圖GS(V′,E′)，簡(jiǎn)稱(chēng)圖GS。其中V′(GS)是V(G)的非空子集，E′(GS)是E(G)的非空子集。顯然V′(GS)是圖G含有的所有最大團(tuán)K|S|的公共頂點(diǎn)集。G-V′表示從G中刪去V′(GS)的所有頂點(diǎn)及其與V′(GS)中頂點(diǎn)關(guān)聯(lián)的一切邊后得到的圖。

定義1若圖G含有的所有最大團(tuán)存在公共頂點(diǎn)，公共頂點(diǎn)的個(gè)數(shù)為k，則稱(chēng)其為第k類(lèi)圖。

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

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

2主要結(jié)果

證明設(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-4的圖G′，由引理2知， χ(G′)=p-4。添上頂點(diǎn)u和v，就得到原來(lái)的圖G，所以圖G的色數(shù)必增加1，即χ(G)=p-3。

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

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

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

證明若圖G是第p-4類(lèi)圖，V′(GS)中任意一個(gè)頂點(diǎn)與V(G-V′)中的所有頂點(diǎn)相鄰，且|S|=p-3，則V(G-V′)中的所有頂點(diǎn)互不相鄰。于是V(G-V′)中的所有頂點(diǎn)必染同一種顏色,而V′(GS)有p-4個(gè)頂點(diǎn)，且是一個(gè)團(tuán),故必染p-4種顏色。因?yàn)閂′(GS)中任意一個(gè)頂點(diǎn)和V(G-V′)中的所有頂點(diǎn)相鄰，所以χ(G)=p-3。

若圖G是第p-6類(lèi)圖，則圖G的所有最大團(tuán)Kp-3有p-6個(gè)公共頂點(diǎn)。因此G-V′有6個(gè)頂點(diǎn)，含最大團(tuán)K3的圖。但圖G-V′中所有最大團(tuán)K3沒(méi)有公共頂點(diǎn)，否則與圖G是第p-6類(lèi)圖矛盾。因此圖G-V′中的所有最大團(tuán)K3有以下4種情況。

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

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

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

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

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

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

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

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

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

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

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

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

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

3進(jìn)一步解決的問(wèn)題

參考文獻(xiàn):

[1] 林妍, 吳瑾, 樊鎖海. 圖著色和標(biāo)號(hào)問(wèn)題的蟻群優(yōu)化算法[J]. 數(shù)學(xué)的實(shí)踐與認(rèn)識(shí), 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] 朱虎, 宋恩民, 路志宏. 求解圖著色問(wèn)題的最大最小蟻群搜索算法[J]. 計(jì)算機(jī)仿真, 2010, 27(3): 190-192, 236.

[6] 安常勝, 馮旭霞. 幾類(lèi)特殊圖的補(bǔ)倍圖的點(diǎn)色數(shù)[J]. 天水師范學(xué)院學(xué)報(bào), 2008, 28(2): 8-9.

[7] 謝繼國(guó), 張效賢, 徐剛. 一類(lèi)6-正則循環(huán)圖的點(diǎn)色數(shù)[J]. 甘肅高師學(xué)報(bào), 2007, 12(5): 1-3.

[8] 達(dá)文姣, 任志國(guó). 扇、輪和完全圖的r(2)點(diǎn)色數(shù)[J]. 甘肅聯(lián)合大學(xué)學(xué)報(bào)(自然科學(xué)版),2011, 25(2): 11-12.

[9] 任志國(guó), 趙傳成, 張忠輔, 等. 關(guān)于Sm∨Fn的邊色數(shù)和點(diǎn)色數(shù)[J]. 蘭州交通大學(xué)學(xué)報(bào)(自然科學(xué)版),2006, 25(4): 147-149.

[10]張忠輔, 王建方, 李正良. 關(guān)于圖的3-色數(shù)[J]. 電子科技大學(xué)學(xué)報(bào), 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] 徐靈姬, 王應(yīng)前. 既不含4-圈又不含6-圈的平面圖的非正常染色[J]. 中國(guó)科學(xué): 數(shù)學(xué), 2013, 43(1): 15-24.

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

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

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

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

[17] 許洋, 張雪媛. 關(guān)于平面圖的3-可染色的一些結(jié)果[J]. 青島農(nóng)業(yè)大學(xué)學(xué)報(bào)(自然科學(xué)版), 2011, 28(1): 75-78.

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

[19] 謝政, 戴麗. 組合圖論[M]. 長(zhǎng)沙:國(guó)防科技大學(xué)出版社, 2003: 4-5, 59.

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

[21] 張祥波. 研究四色問(wèn)題的意義及理論構(gòu)想[J]. 數(shù)學(xué)理論與應(yīng)用, 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

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

中圖分類(lèi)號(hào)：O157.5

文獻(xiàn)標(biāo)識(shí)碼：A

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

作者簡(jiǎn)介：張祥波，男，山東臨邑人，臨盤(pán)中學(xué)一級(jí)教師，研究方向?yàn)閳D的染色。

收稿日期：2014-09-25

網(wǎng)絡(luò)出版時(shí)間：2015-8-25 15:40網(wǎng)絡(luò)出版地址：http://www.cnki.net/kcms/detail/34.1150.N.20150825.1540.004.html