關于非平面圖染色的一個猜想

2017-06-28 15:09:33張祥波

山東科學 2017年3期

張祥波

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

關于非平面圖染色的一個猜想

張祥波

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

四色問題;頂點染色數;圖的厚度;平面圖

1 引言及預備知識

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

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

定義1[2]如果圖G含有的所有最大團存在公共頂點，且公共頂點的個數為k，則稱此圖為第k類圖。

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

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

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

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

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

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

則χ(G)=p-3。

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

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

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

2 主要結果及證明

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

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

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

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

綜上，定理為真。證畢。