張祥波

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

?

關(guān)于非平面圖染色的一個(gè)猜想

張祥波

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

四色問題;頂點(diǎn)染色數(shù);圖的厚度;平面圖

1 引言及預(yù)備知識(shí)

平面圖的染色由于四色問題的計(jì)算機(jī)證明[3-5]，而倍受國內(nèi)外學(xué)者的廣泛關(guān)注。而非平面圖的染色由于缺少這樣一個(gè)有價(jià)值和意義的問題，至今尚無進(jìn)展。對(duì)于非平面圖的染色，文獻(xiàn)[6]猜想：χ(G)≤4θ(G)+θ2(G)-1。文獻(xiàn)[7-9]證明了下述定理。

以下給出本文證明中用到的引理和定義。

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

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

①若該公共頂點(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。

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

(2)圖G是第p-4類圖或第p-6類圖；

則χ(G)=p-3。

(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 主要結(jié)果及證明

(1)p=7時(shí)，圖G是頂點(diǎn)數(shù)等于7，含最大團(tuán)K2的圖。將圖G中一對(duì)不相鄰頂點(diǎn)u和v刪掉后，必能得到一個(gè)頂點(diǎn)數(shù)是5，含最大團(tuán)K2的圖G1或僅有5個(gè)頂點(diǎn)的無邊圖。若圖G1不存在奇圈，由引理1知，則圖G1是二部圖。于是χ(G1)=2，將u和v添上，色數(shù)最多增加1，故χ(G)≤3。若圖G1存在奇圈，則圖G1是一個(gè)5-圈，于是χ(G1)=3。而u至多和圖G1中2個(gè)不相鄰頂點(diǎn)相鄰，于是u可以用圖G1中的顏色染之。v的情況同u，v與u不相鄰，故χ(G)≤3。

(2)p=8時(shí)，圖G是頂點(diǎn)數(shù)等于8，含最大團(tuán)K3的圖。將圖G中2個(gè)不相鄰的頂點(diǎn)u和v刪掉，必能得到頂點(diǎn)數(shù)是6，含最大團(tuán)K3的圖，記作G1?？紤]圖G1的色數(shù)，若圖G1中所有最大團(tuán)K3存在1個(gè)公共頂點(diǎn)，由引理2情況①或③知，則χ(G1)=3。于是χ(G)≤4。由引理2情況②知，χ(G1)=4。設(shè)圖G1中所有最大團(tuán)K3的公共頂點(diǎn)是w，若u與w相鄰，則u至多與圖G1-w中2個(gè)不相鄰頂點(diǎn)相鄰。而圖G1-w是5-圈，故χ(G1-w)=3。所以u(píng)一定可以用圖G1-w中的一種顏色染之。若u與w不相鄰，則u與w可染同一種顏色。由于u與v不相鄰，頂點(diǎn)v的情況與u相同，故頂點(diǎn)v的染色不影響圖G的色數(shù)，所以χ(G)=4。若圖G1中所有最大團(tuán)存在2個(gè)公共頂點(diǎn)，由引理3知，χ(G1)=3，故χ(G)≤4。若圖G1所有最大團(tuán)K3不存在公共頂點(diǎn)，由引理4知，χ(G1)=3。故χ(G)≤4。

(3)p=9時(shí)，圖G是頂點(diǎn)數(shù)等于9，含最大團(tuán)K4的圖。將圖G中2個(gè)不相鄰頂點(diǎn)u和v刪掉，必能得到頂點(diǎn)數(shù)是7，含最大團(tuán)K4的圖，記作圖G1。由定義1和引理9知，圖G1有且僅有以下幾類圖：第1類圖、第2類圖、第3類圖及只含有一個(gè)最大團(tuán)K4的圖?？紤]圖G1的色數(shù)，不外乎以下幾種情況：若圖G1分別滿足引理5、引理6、引理7的條件，則由引理5、引理6、引理7分別知，χ(G1)=4；將頂點(diǎn)u和v添上，故χ(G)≤5。若圖G1滿足引理8的條件，則G1-V′是頂點(diǎn)數(shù)為5，含最大團(tuán)K2的圖。若圖G1-V′不存在奇圈，故χ(G1)=4，將頂點(diǎn)u和v添上，于是χ(G)≤5。若圖G1-V′存在奇圈，故χ(G1)=5。考慮頂點(diǎn)u，若u與V′中所有頂點(diǎn)相鄰，則u至多與G1-V′中2個(gè)不相鄰頂點(diǎn)相鄰，從而u可以用圖G1-V′中的顏色染之。若u與V′中至少一個(gè)頂點(diǎn)不相鄰，則u總可以用V′中的顏色染之。v與u不相鄰，v的情況同u，故χ(G)=5。

(4)p=10時(shí)，圖G是頂點(diǎn)數(shù)等于10，含最大團(tuán)K5的圖。將圖G中2個(gè)不相鄰頂點(diǎn)u和v刪掉，必得到頂點(diǎn)數(shù)是8，含最大團(tuán)K4或K5的圖G1。若圖G1含最大團(tuán)K4，由引理10知，χ(G1)≤5。添上頂點(diǎn)u和v，就得到原來的圖G。而頂點(diǎn)染色數(shù)最多增加1，故χ(G)≤6。若圖G1含最大團(tuán)K5，分別由引理5、引理6、引理7知，χ(G1)=5。添上頂點(diǎn)u和v，故χ(G)≤6。若圖G1滿足引理8條件，G1-V′不存在奇圈，則χ(G1)=5。于是χ(G)≤6。G1-V′存在奇圈，則χ(G1)=6。u和v的情況同(3)，于是χ(G)=6。

綜上，定理為真。證畢。

證明 考慮以下幾種情況:

3 結(jié)語

[1]BONDY J, MURTY U. Graph theory[M]. Berlin: Springer, 2008.

[2] 張祥波. 一類特殊圖的頂點(diǎn)染色數(shù)[J]. 安慶師范學(xué)院學(xué)報(bào)(自然科學(xué)版), 2015, 21(3): 11-13.

[3] APPEL K, HAKEN W. The solution of the four-color map problem[J]. Sci Amer,237(1977):108-121.

[4] APPEL K, HAKEN W, KOCH J. Every planar map is four-colorable. I: Discharging[J]. Illinois J Math, 1977 (21):429-490。

[5]APPEL K, HAKEN W. Every planar map is four-colorable. Ⅱ: Reducibility[J]. Illinois J Math, 1977 (21):491-561.

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

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

[8] 張祥波. 一類特殊圖的頂點(diǎn)染色及其猜想的證明[J].重慶工商大學(xué)學(xué)報(bào)(自然科學(xué)版)，2015,32(9):66-70.

[9] 張祥波.與圖的頂點(diǎn)染色數(shù)有關(guān)的幾個(gè)問題[J]. 高師理科學(xué)刊，2016,36(3)：17-20.

[10] 謝政,戴麗. 組合圖論[M]. 長(zhǎng)沙:國防科技大學(xué)出版社，2003.

[11] 卜月華,吳建專,顧國華，等. 圖論及其應(yīng)用[M]. 南京:東南大學(xué)出版社, 2002.

A conjecture about coloring of non-planar graphs

ZHANG Xiang-bo

(Linpan Middle School,Dezhou 251507，China)

∶four-color problem； vertex coloring number； thickness of a graph； planar graphs

10.3976/j.issn.1002-4026.2017.03.016

2016-04-27

張祥波(1978—)，男，研究方向?yàn)閳D的染色。E-mail:lpzx2010@126.com.

O157.5

A

1002-4026(2017)03-0094-04