毛惠群

(浙江師范大學(xué)數(shù)學(xué)系， 浙江金華 321004)

1 引言

本文考慮的圖都是簡(jiǎn)單無(wú)向圖.G=(V,E)是一個(gè)以V為頂點(diǎn)集、E為邊集的圖.G的一個(gè)(c1,c2, …,ck)-染色是一個(gè)映射φ：V︳→{1, 2, …,k}， 使得對(duì)每一個(gè)i∈{1, 2, …,k}， 子圖G[Vi]的最大度至多為ci， 其中Vi={v∈V|φ(Vi)=i}.運(yùn)用這個(gè)概念， 著名的四色定理[1]可表述為： 每一個(gè)平面圖是(0, 0, 0, 0)-可染的；Eaton[2]和Hull證明了每個(gè)平面圖是(2, 2, 2)-可染的.Gr?tzsch[3]的三色定理為： 每個(gè)不含三角形的平面圖是(0, 0, 0)-可染的.Steinberg猜想[4]為: 每個(gè)既沒有4圈又沒有5圈的平面圖是(0, 0, 0)-可染的. 根據(jù)Steinberg猜想， 已取得一些結(jié)果： 王應(yīng)前等人證明了每個(gè)既沒有4圈又沒有5圈的平面圖是(1, 1, 0)-可染[5]的以及(3, 0, 0)-可染的[6]； 2017年， Cohen-Addad[7]等人已經(jīng)列舉出反例說(shuō)明Steinberg猜想是錯(cuò)誤的. 就對(duì)圖的非正常染色的定義， 該領(lǐng)域已得到廣泛的研究. 比如對(duì)相鄰短圈的研究， 并得出許多有意義的結(jié)果： 王應(yīng)前[8]等人證明了沒有相鄰5—圈的平面圖是(1, 1, 0)-可染的； 李[9]等人證明了沒有6圈和沒有相鄰4—_圈的平面圖是(1, 1, 0)-可染的； Hoskins[10]等人證明了沒有4圈和相鄰三角形的平面圖是(2, 0, 0)-可染的. 根據(jù)對(duì)以上問(wèn)題的研究， 學(xué)者提出了如下一些問(wèn)題.

問(wèn)題設(shè)圖G為一個(gè)不含相鄰4—圈的平面圖， 則

(1)圖G是(1, 1, 0)-可染的；

(2)圖G是(1, 0, 0)-可染的.

2 定理及其證明

定理1設(shè)圖G是不含相交3圈， 且不含相鄰4—圈的平面圖， 那么G是(2, 2, 0)-可染的.

本文考慮的圖都是有限的、 簡(jiǎn)單的、 無(wú)向的. 如果一個(gè)圖形G可以嵌入到平面中, 使其邊緣只在其兩端相交， 則稱圖G為平面圖. 分別用V,E,F表示圖G的點(diǎn)集、 邊集和面集， 圖G記作圖G=(V,E,F). 對(duì)任意的一個(gè)頂點(diǎn)v∈V,v的度數(shù)記作d(v). 稱v分別為k-點(diǎn)，k--點(diǎn)和k+-點(diǎn)， 如果d(v)=k,d(v)≤k和d(v)≥k. 對(duì)任意點(diǎn)u,v∈V, 稱uv∈E為圖G的一條(d(u),d(v))-邊，u稱為v的 一個(gè)d(u)-鄰點(diǎn). 對(duì)任意的一個(gè)面f∈F,f的度數(shù)記作d(f). 稱f分別為k-面、k--面和k+-面， 如果d(f)=k,d(f)≤k和d(f)≥k. 稱f為一個(gè)(d(v1),d(v2), …,d(vk))-面， 如果f上的點(diǎn)v1,v2, …,vk是按某一時(shí)針?lè)较蜻B續(xù)出現(xiàn)的. 如果一個(gè)點(diǎn)或一條邊與一個(gè)三角形相關(guān)聯(lián)， 則稱這個(gè)點(diǎn)或這條邊是三角的. 稱點(diǎn)v是d(u)-鄰點(diǎn)m-面的， 如果v有一個(gè)鄰點(diǎn)u, 且v和鄰點(diǎn)u與一個(gè)m-面相關(guān)聯(lián). 稱點(diǎn)v是k-三角的， 如果v關(guān)聯(lián)k個(gè)三角形， 用fm(v)表示與v-點(diǎn)相關(guān)聯(lián)的m-面的個(gè)數(shù). 我們稱點(diǎn) 為5b-點(diǎn)， 如果5-點(diǎn)v關(guān)聯(lián)一個(gè)(3, 5, 6+)-面， 且另外三個(gè)點(diǎn)為3-點(diǎn).

2.1 極小反例的結(jié)構(gòu)性質(zhì)

引理1δ(G)≥3.

證明反設(shè)v有兩個(gè)鄰點(diǎn)v1和v2. 由G的極小性，G-v有一個(gè)(2, 2, 0)-染色φ.v的兩個(gè)鄰點(diǎn)至多使用兩種顏色染好， 此時(shí)v可用第三種顏色染好， 則得到G的一個(gè)(2, 2, 0)-染色， 這與G的選取矛盾.

引理2G中非三角3點(diǎn)v至多只有一個(gè)4—-鄰點(diǎn).

證明反設(shè)v有兩個(gè)4—-鄰點(diǎn)v1和v2, 令v3為v的另一個(gè)鄰點(diǎn). 由G的極小性,G-v有一個(gè)(2, 2, 0)-染色φ. 可斷言v的3個(gè)鄰點(diǎn)必染不同的顏色， 否則v正常染好. 此時(shí)v1和v2中至少有一個(gè)點(diǎn)可染顏色1或顏色2. 由對(duì)稱性, 不妨令φ(v1)=1, 則{1, 1, 2}∈φ(N(v1)v), 否則v直接染顏色1或者改染v1為2,v染1. 這時(shí)，v1改染顏色3, 再把v染1, 則得到G的一個(gè)(2, 2, 0)-染色， 這與G的選取矛盾.

引理3設(shè)uv是一條(3, 3)-邊， 且w是u,v的公共鄰點(diǎn)， 則d(w)≥6.

證明反設(shè)d(w)≤5, 不妨設(shè)d(w)=5. 由G的極小性，G-u有一個(gè)(2, 2, 0)-染色φ. 可斷言u(píng)的3 個(gè)鄰點(diǎn)必染不同的顏色， 否則u正常染好. 令u′為u的另一個(gè)鄰點(diǎn)， 若φ(u′)=3, 則u染與v相同的顏色. 故φ(u′)≠3, 由對(duì)稱性， 不妨設(shè)φ(u′)=1. 如果φ(v)=2, 則u染顏色2； 故φ(v)=3, 則v的外鄰點(diǎn)v′必染1, 否則v改染為1,u染3； 此時(shí)，φ(w)=2, 且{2, 2, 1}∈φ(N(w)v), 否則 直u接染顏色2或者改染w為1,u染顏色2. 此時(shí)w改染顏色3,v改染為顏色2,u染顏色2, 則得到G的一個(gè)(2, 2, 0)-染色， 這與G的選取矛盾.

引理45-點(diǎn)v至多有4個(gè)3-鄰點(diǎn).

證明反設(shè)5-點(diǎn)v有5個(gè)5-鄰點(diǎn)vi(i=1, 2, 3, 4, 5). 由G的極小性，G-{v,v1,v2, …,v5}有—個(gè)(2, 2, 0)-染色φ. 先按順序依次正常染好vi(i=1, 2, 3, 4, 5). 如果

{1, 2, 3}?φ(N(v)), 則v正常染好， 所以

{1, 2, 3}∈φ(N(v)). 可斷言{1, 1, 2, 2, 3}∈φ(N(v)), 否則用沒有出現(xiàn)的顏色去染v. 現(xiàn)在用1或2去染v, 則得到G的一個(gè)(2, 2, 0)-染色， 這與G的選取矛盾.

引理5設(shè)5-點(diǎn)v關(guān)聯(lián)一個(gè)(3, 5,d(u))-面， 且其他鄰點(diǎn)為3-鄰點(diǎn)， 則u為6+-點(diǎn).

證明反設(shè)u為5--點(diǎn)， 不妨令d(u)=5. 令v的其他鄰點(diǎn)分別為vi(i=1, 2, 3, 4)且d(v1)=d(v2)=d(v3)=d(v4)=3, 其中v4與u相鄰， 且v4的外鄰點(diǎn)為v41. 由G的極小性，G-{v,v1,v2,v3,v4}有一個(gè)(2, 2, 0)-染色φ. 先按順序依次正常染好vi(i=1, 2, 3, 4).

顯然{1, 2, 3}∈φ(N(v)), 否則v能夠正常染好. 如果φ(u)=3, 則給v染{1, 2}兩種顏色在N(v)中至多只出現(xiàn)兩次. 故φ(u)≠3, 由對(duì)稱性， 不妨令φ(u)=1. 此時(shí)分為兩種情況.

1) 如果φ(v4)=3, 則

{2, 2, 2}∈φ(N(v){v4,u}), 否則v染2, 此時(shí)v41必染2, 否則v4改染為2,v染3;{1, 1, 2}∈φ(N(u)v4), 否則v直接染1或u改染為2, 再把v染1, 此時(shí)u改染為顏色3,v4改染為顏色1,v染顏色 1.

2) 當(dāng)φ(v4)=2,{2, 2, 3}∈φ(N(u){v4,u}), 否則v染沒有出現(xiàn)的那個(gè)顏色.φ(v41)=3, 否則v4改染為顏色 3,v染顏色2.

{1, 1, 3}∈φ(N(u)v4), 否則v直接染1或u改染為顏色3,v染1, 此時(shí)u改染為顏色2,v染1.

綜上分析， 則得到G的一個(gè)(2, 2, 0)-染色， 這與G的選取矛盾.

引理66-點(diǎn)v至多有5個(gè)3-鄰點(diǎn).

證明反設(shè)6-點(diǎn)v有6個(gè)3-鄰點(diǎn)vi(i=1, 2, 3, 4, 5, 6). 由G的極小性，G-{v,v1,v2, …,v6}有一個(gè)(2, 2, 0)-染色φ. 先按順序依次正常染好vi(i=1, 2, 3, 4, 5, 6). 可斷言{1, 1, 1, 2, 2, 2}∈φ(N(v)), 否則用沒有出現(xiàn)的那個(gè)顏色去染v. 此時(shí)， 用顏色3去染v, 則得到G的一個(gè)(2, 2, 0)-染色， 這與G的選取矛盾.

引理7設(shè)6-點(diǎn)v的鄰點(diǎn)分別為vi(i=1, 2, 3, 4, 5, 6), 其中d(v1)=d(v2)=d(v3)=d(v4)=d(v5)=3, 且v5與v6相鄰， 則v6不為5b-點(diǎn).

證明反設(shè)v6為5b-點(diǎn). 且v61,v62,v63是v6的 3個(gè)3-鄰點(diǎn)， 則d(v61)=d(v62)=d(v63)=3.G的極小性，G-{v,v1,v2,v3,v4,v5,v6,v61,v62,v63}有一個(gè)(2, 2, 0)-染色φ. 先按順序依次正常染好v1,v2,v3,v4,v61,v62,v63. 首先用{1, 2}顏色中至多只出現(xiàn)—次的顏色去染v6, 然后再正常染v5. 可斷言{1, 1, 1, 2, 2, 2}∈φ(N(v)), 否則用沒有出現(xiàn)的那個(gè)顏色去染v. 此時(shí)用顏色3去染v, 則得到G的一 個(gè)(2, 2, 0)-染色， 這與G的選取矛盾.

2.2 定理1的證明

假設(shè)定理1不成立. 設(shè)G=(V,E)是定理1關(guān)于頂點(diǎn)數(shù)最少的一個(gè)極小反例. 那就是說(shuō)，G本身不是(2, 2, 0)-可染的， 但每個(gè)少于G的頂點(diǎn)數(shù)的子圖都是(2, 2, 0)-可染的. 將G嵌入平面， 則得到平面圖G=(V,E,F), 其中V為G的點(diǎn)集、E為G的邊集、F為G的面集， 且具有上述所有結(jié)構(gòu)性質(zhì). 我們首先假設(shè)G是2-連通的情況， 因此G的每一個(gè)面都是簡(jiǎn)單的. 接下來(lái)， 我們將規(guī)定權(quán)轉(zhuǎn)移規(guī)則來(lái)推出矛盾， 進(jìn)而證明定理1在2-連通時(shí)是成立的.

對(duì)連通平面圖G， 由歐拉公式， 有

|V(G)|-|E(G)|+|F(G)|=2

對(duì)每一個(gè)x∈V(G)∪F(G)， 定義其初始權(quán)值為ch(x). 對(duì)任意v∈V(G)， 定義ch(v)=d(v)-6， 而對(duì)于f∈F(G)，ch(f)=2d(f)-6， 則

x∈V(G)∪F(G)， 都有ch′(x)≥0. 由于只在頂點(diǎn)和面之間進(jìn)行權(quán)轉(zhuǎn)移， 故權(quán)總和不變， 從而與

權(quán)轉(zhuǎn)移規(guī)則如下：

(2) 設(shè)v為3-點(diǎn)， 且v1,v2,v3均為v的鄰點(diǎn)， 設(shè)d(v2)，d(v3)=5+， 則

下面驗(yàn)證新權(quán)ch′(x)≥0，x∈V(G)∪F(G).

首先檢驗(yàn)面的新權(quán)， 即

ch′(f)≥0，?f∈F(G).

設(shè)d(f)=5+， 由(1)，知

設(shè)d(f)=4， 由(1)，知

設(shè)d(f)=3， 由權(quán)轉(zhuǎn)移規(guī)則， 沒有進(jìn)行權(quán)轉(zhuǎn)入和權(quán)轉(zhuǎn)出， 所以ch′(f)=2d(f)-6=0.

接下來(lái)驗(yàn)證點(diǎn)的最終權(quán)滿足

ch′(v)≥0，?v∈V(G).

用fk(v)表示與v點(diǎn)相關(guān)聯(lián)的k-面的個(gè)數(shù). 因?yàn)镚沒有相交 -圈， 因此對(duì)任意v∈V(G)，f3(v)≤1.因?yàn)镚中4—圈不相鄰， 因此與4—圈相鄰的面均是5+-面.

設(shè)d(v)=4. 由權(quán)轉(zhuǎn)移規(guī)則， 4-點(diǎn)不向外轉(zhuǎn)權(quán). 若f3(v)=0， 則f4(v)≤2， 從而有

故f3(v)≠0. 令f3(v)=1， 則f4(v)≤1，

設(shè)d(v)=5.易知f4(v)≤2.由于5-點(diǎn)至多與 4 個(gè) 3-點(diǎn)相鄰. 若f3(v)=0， 如果f4(v)=0， 由權(quán)轉(zhuǎn)移規(guī)則(1)和(2)， 有

若f4(v)=1， 由權(quán)轉(zhuǎn)移規(guī)則(2)，知

若f4(v)=1且v不為5b-點(diǎn)， 由權(quán)轉(zhuǎn)移規(guī)則(2)，知

如果v不為5b-點(diǎn)， 顯然，v至多與3個(gè)3-鄰點(diǎn)， 則

綜合以上各種情況， 得到如下矛盾的式子

上面的這個(gè)矛盾說(shuō)明G不存在， 因此證明了定理1在G是2-連通時(shí)成立.

現(xiàn)在我們假設(shè)G不是2-連通的， 也就是說(shuō)G有割點(diǎn). 我們可以選取G的一個(gè)分塊B， 令為G在B上的唯一割點(diǎn)， 令f0為B的外表面. 因?yàn)棣?G)≥3， 所以平面圖B是2-連t*通的. 因此，B的每個(gè)面的邊界都是一個(gè)圈，B的每個(gè)頂點(diǎn)v都與dB(v)個(gè)不同的面相關(guān)聯(lián). 顯然，B既沒有相交3-圈， 也沒有相鄰4—圈. 而且，G從引理2.1到引理2.7所建立的每一個(gè)性質(zhì)只有在涉及到t*時(shí)不成立. 我們可以在B=(V(B),E(B),F(B))進(jìn)行如下權(quán)轉(zhuǎn)移規(guī)則.

初始權(quán)定義為： 對(duì)每一個(gè)x∈V(B)∪F(B)， 定義其初始權(quán)值為ch(x)=dB(v)-6.

由握手定理

和歐拉公式|V(G)|-|E(G)|+|F(G)|=2， 有

我們根據(jù)下列規(guī)則重新分配x∈V(B)∪F(B)的權(quán)ch(x).

r3. 對(duì)于x≠t*，f0, 我們按照G是2-連通的權(quán)轉(zhuǎn)移規(guī)則(1)、 (2).

顯然， 當(dāng)B是2-連通時(shí)，

對(duì)x∈{V(B)∪F(B)}{t*,f0}能通過(guò)(1)、 (2)證明ch′(x)=dB(x)-6≥0. 對(duì)于t*和f0， 由r1和dB(t*)≥2， 有

由r2和dB(f0)≥3， 有

因此

從而證明了當(dāng)G不是2-連通時(shí)定理1也成立. 因此， 定理1成立.