稀疏圖的(3,4)-染色

胡黎莉

（閩南師范大學數學與統計學院,福建漳州 363000）

僅考慮有限簡單圖.沿用文獻[1]的記號，除非另有說明.

若圖G的頂點集可以分為V1和V2兩部分，使得在G的導出子圖G[V1]和G[V2]中，頂點的最大度分別是d1和d2，則稱G是(d1,d2)-可染色的.令g(G)表示圖G的圍長并令.Βorodin等[2]證明了mad(G)＜7/3的圖G是(1,0)-可染的.Choi等[3]證明了圍長大于等于5的平面圖是(3,5)-可染的.Choi 等[4]證明了圍長大于等于5 的平面圖是(3,4)-可染的.Βorodin 等[5]證明了圍長大于等于5 的平面圖是(2,6)-可染的.

證明了以下結果.

定理1若圖G滿足mad(G)＜19/6，則G是(3,4)-可染的.

由于平面圖G滿足,故由定理1可得以下推論.

推論1圍長大于等于6的平面圖是(3,4)-可染的.

1 預備知識和引理

稱度為d(≥d,≤d)的頂點為d-度點(d+-點,d--點).設v∈V(G)，若v有一個鄰點u的度為d，則稱u是v的d-鄰點.對于5 ≤k≤7,如果一個k-度點和k-1個2-度點相鄰，則稱它是壞-點.輕-點是2-度點或壞點.

設G是定理的一個反例，使得|V(G)|最小.顯然，G連通且δ(G)≥2.令i∈{3,4}且c是G或G的子圖的一個染色.若c(v)=i且v有i個鄰點染顏色i，則稱v是i-飽和的.根據定義，一個i-飽和點至少有i個鄰點.用顏色3和4給G的某個子圖染色，使得染顏色i的所有頂點的導出子圖的最大度至多是i(i∈{3,4}).

引理1若d(v)=2,則v和兩個5+-點相鄰,且其中一個是6+-點.

證明設N(v)={v1,v2}.由G的極小性知G-v有一個(3,4)-染色c.若c(v1)=c(v2),則v可正常染色,矛盾.不失一般性，假設c(v1)=3且c(v2)=4.由于令c(v)=3不能得到G的一個(3,4)-染色，故v1是3-飽和點；由于令c(v1)=4和c(v)=3不能得到G的一個(3,4)-染色，故v1有一個4-飽和鄰點.因此，d(v1)≥5.同理可證，d(v2)≥6.

引理2若d(v)=3,則v至少和兩個5+-點相鄰,且其中一個是6+-點.

證明設N(v)={u,v3,v4}.由G的極小性知G-v有一個(3,4)-染色c.若c(u)=c(v3)=c(v4),則v可正常染色,矛盾.不失一般性，假設c(v3)=3且c(v4)=4.進一步假設c(u)=i，其中i∈{3,4}且j∈{{3,4} {i}}.

由于令c(v)=j不能得到G的一個(3,4)-染色，故vj是j-飽和的；由于令c(vj)=i和c(v)=j不能得到G的一個(3,4)-染色，故vj有一個鄰點染顏色i.從而，d(vj)≥j+2.由于令c(v)=i不能得到G的一個(3,4)-染色,故u或vi是i-飽和點.若d(u)≤i+1 且d(vi)≤i+1,則給{u,vi}中的i-飽和點重新染顏色j并令c(v)=i，得到G的一個(3,4)-染色，矛盾.因此，u和vi至少有一個是(i+2)+-點.

引理3若d(v)≤8,則v至少和一個5+-點相鄰.

證明用反證法.假設v的鄰點都是4--點.由G的極小性知G-v有一個(3,4)-染色c.顯然顏色3和4都必須出現在N(v)的染色中,否則v可正常染色,矛盾.由于v的鄰點都是4--點，故v不能和4-飽和點相鄰；由于令c(v)=4不能得到G的一個(3,4)-染色，故v至少有5個鄰點染顏色4；由于令c(v)=3不能得到G的一個(3,4)-染色且d(v)≤8，故v有一個3-飽和鄰點.又因為v的鄰點都是4--點，可以重新給v的3-飽和鄰點分配顏色4再給v染顏色3，由此得到G的一個(3,4)-染色，矛盾.

引理4G中的每個5--點至少和一個6+-點相鄰.

證明用反證法.假設v是G中的一個5--點，它的鄰點都是4--點.由G的極小性知，G-v有一個(3,4)-染色.顯然顏色3 和4 均出現在N(v)的顏色中,否則v可正常染色,矛盾.給v染顏色4.這種染色方式會出現的唯一一個問題是存在v的鄰點，記作u，它染顏色4 且有5 個鄰點染顏色4.由于d(u)≤5，可以重新給u染顏色3.對于v的這類鄰點我們都重復這一過程，最終得到G的一個(3,4)-染色，矛盾.

引理5G中的6-度點不能和6個輕-點相鄰.

證明用反證法.假設v是G中的一個6-度點，它的鄰點都是輕-點.由G的極小性知，G-v有一個(3,4)-染色.若v存在2-鄰點，則先對v的2-鄰點重新正常染色.如果v至多有4 個鄰點染顏色4，則給v染顏色4.這種染色方式會出現的唯一一個問題是存在v的鄰點，記作u，它染顏色4 且有5 個鄰點染顏色4.由于d(u)≤7，可以重新給u染顏色3.因此，假設v至少有5個鄰點染顏色4并給v染顏色3.這種染色方式會出現的唯一一個問題是存在v的壞鄰點，記作w，它染顏色3且有4個鄰點染顏色3.由于d(w)≤7，可以重新給w染顏色4，最終得到G的一個(3,4)-染色，矛盾.

引理6G中的兩個壞-點不能相鄰.

證明用反證法.假設u和v是G中的兩個壞-點且uv∈E(G).在G中刪去u,v及它們的鄰點，所得的圖記為G′.由G的極小性知G′有一個(3,4)-染色.先給u和v的2-鄰點正常染色.由于d(u)≤7，存在i∈{3,4}，使得u至多有3個鄰點染顏色i.給u染顏色i.類似地，可以給v染顏色j∈{3,4}，由此得到G的一個(3,4)-染色，矛盾.

引理7假設d(v)=5且v有3個2-鄰點，則：

1)如果v有一個3-鄰點，則v不能和壞的6-度點相鄰.

2)v不能和兩個壞的6-度點相鄰.

證明1)用反證法.假設v有一個3-鄰點和一個壞的6-鄰點，記作u.在G中刪去u和v，所得的圖記為G′.由G的極小性知G′有一個(3,4)-染色.先給u和v的2-鄰點重新正常染色.由于d(u)=6，存在i∈{3,4}，使得u至多有2個鄰點染顏色i.給u染顏色i.如果v的所有鄰點都染相同的顏色，則v可正常染色，矛盾.因此，假設顏色3和4均出現在N(v)的顏色中.可以給v染顏色4,由此得到G的一個(3,4)-染色，矛盾.

2)否則，假設v有兩個壞的6-鄰點，記作u1和u2.由G的極小性知，G-v有一個(3,4)-染色.先對v的2-鄰點重新正常染色.由于d(v)=5，存在i∈{3,4}，使得v至多有2 個鄰點染顏色i.給v染顏色i.這種染色方式會出現的唯一一個問題是u1（或u2）染顏色i且有i+1個鄰點染顏色i.由于d(u1)=6(d(u2)=6)，可以給u1（或u2）重新分配顏色{3,4}{i}.易見G中染顏色3（或4）的頂點的導出子圖的最大度依舊不超過3（或4），于是得到G的一個(3,4)-染色，矛盾.

引理8假設d(v)=6且v有4個2-鄰點，則：

1)v不能和兩個壞的5-度點相鄰.

2)如果v和一個壞的5-度點相鄰，則v不能和3-度點或壞的6-度點相鄰.

證明1)否則，假設v有兩個壞的5-鄰點，記作u1和u2.由G的極小性知，G-v有一個(3,4)-染色.先對v的2-鄰點重新正常染色.由于d(v)=6，存在i∈{3,4}，使得v至多有3 個鄰點染顏色i.給v染顏色i.這種染色方式會出現的唯一一個問題是u1（或u2）染顏色i且有i+1 個鄰點染顏色i.由于d(u1)=5(d(u2)=5)，我們可以給u1（或u2）重新分配顏色{3,4}{i}，進而得到G的一個(3,4)-染色，矛盾.

2)記v的壞5-鄰點為u.用反證法.首先假設v和一個3-度點相鄰.由G的極小性知，G-v有一個(3,4)-染色.先對v的2-鄰點重新正常染色.由于d(v)=6，存在i∈{3,4}，使得v至多有3個鄰點染顏色i.給v染顏色i.這種染色方式會出現的唯一一個問題是u染顏色i且有i+1個鄰點染顏色i.由于d(u)=5，可以給u重新分配顏色{3,4}{i}，進而得到G的一個(3,4)-染色，矛盾.

假設v和一個壞的6-度點w相鄰.由G的極小性知，G-v有一個(3,4)-染色.先對v的2-鄰點重新正常染色.由于d(v)=6，存在i∈{3,4}，使得v至多有3 個鄰點染顏色i.給v染顏色i.這種染色方式會出現的唯一一個問題是u（或w）染顏色i且有i+1 個鄰點染顏色i.由于d(u)=5(d(w)=6)，可以給u（或w）重新分配顏色{3,4}{i}，進而得到G的一個(3,4)-染色，矛盾.

引理9假設d(v)=7且v有5個2-鄰點，則v不能和兩個壞的5-度點相鄰.

證明用反證法.假設v有兩個壞的5-鄰點，記作u1和u2.由G的極小性知，G-v有一個(3,4)-染色.先對v的2-鄰點重新正常染色.由于d(v)=7，存在i∈{3,4}，使得v至多有3個鄰點染顏色i.給v染顏色i.這種染色方式會出現的唯一一個問題是u1（或u2）染顏色i且有i+1 個鄰點染顏色i.由于d(u1)=5(d(u2)=5)，可以給u1（或u2）重新分配顏色{3,4}{i}，進而得到G的一個(3,4)-染色，矛盾.

2 定理1的證明

下面將采用權轉移方法導出矛盾，從而完成定理的證明.對于任意的v∈V(G)，假設v的初始權值為w(v)=6d(v)-19.由mad(G)＜19/6可得.然后根據權轉移規則，重新分配頂點的權，v的最終權記為w′(v).

權轉移規則如下：

R1.G的每個5+-點向其每個2-鄰點轉移權值7/2.

R2.G的每個4+-點向其每個3-鄰點轉移權值1/2.

R3.G的每個6+-點向其每個相鄰的壞5-度點轉移權值3.

R4.G的每個5+-點向其每個相鄰的壞6-度點轉移權值1/2.

為了方便起見，記v的2-鄰點的個數為t.下面分7種情況討論：

1)若d(v)≥8,則根據R1～R4，w′(v)≥6d(v)-19-7/2d(v)=5/2d(v)-19 ≥1.

2)假設d(v)=7.首先假設v是壞點，則t=6 且由引理3 和引理6 知，v和一個5+-點相鄰且該點不是壞點.由R1 得，w′(v)≥6×7-19-6×7/2=2.設v不是壞點，則t≤5.若t≤4,則由R1～R4，w′(v)≥6×7-19-4×7/2-3×3=0.若t=5，則由引理9 可知，v至多和一個壞的5-度點相鄰.從而，根據R1～R4，w′(v)≥6×7-19-5×7/2-3-1/2=2.

3)假設d(v)=6.首先假設v是壞點，則t=5 且由引理3 和引理6 知，v和一個5+-點相鄰且該點不是壞點.根據R1 和R4，w′(v)≥6×6-19-5×7/2+1/2=0.假設v不是壞點，則t≤4.令t=4.若v不與壞的5-度點相鄰，則w′(v)≥6×6-19-4×7/2-2×1/2=2.若v有壞的5-鄰點，則由引理8 知，這樣的鄰點只有一個且v不能和3-度點或壞的6-度點相鄰.從而，由R1和R3得，w′(v)≥6×6-19-4×7/2-3=0.當t≤3時，由引理5可知,v至少有一個鄰點不是輕-點.從而，當1 ≤t≤3 時，由R1～R4 可得w′(v)≥6×6-19-3×7/2-2×3-1/2=0；當t=0時，由R2～R4可得w′(v)≥6×6-19-3×5-1/2=3/2.

4)假設d(v)=5.首先假設v是壞點，則t=4 且由引理4 和引理6 知，v和一個6+-點相鄰且該點不是壞點.根據R1 和R3，w′(v)≥6×5-19-4×7/2+3=0.現假設v不是壞點，則t≤3.若t≤2,則由R1,R2 和R4 可得，w′(v)≥6×5-19-2×7/2-3×1/2=5/2.假設t=3.若v既沒有3-鄰點也沒有壞的6-鄰點，則根據R1～R4,w′(v)≥6×5-19-3×7/2=1/2.假設v有一個3-鄰點,則由引理7(1)，v不能和壞的6-度點相鄰.因此，根據R1,R2 和R4,w′(v)≥6×5-19-3×7/2-1/2=0.若v有一個壞的6-鄰點,則根據引理7 知，v的最后一個鄰點不是壞的6-度點也不是3-度點.從而，根據R1,R2 和R4,w′(v)≥6×5-19-3×7/2-1/2=0.

5)若d(v)=4,則根據R2，w′(v)≥6×4-19-4×1/2=3.

6)若d(v)=3,則由引理2知，v至少和兩個5+-點相鄰.從而，根據R2,w′(v)≥6×3-19+2×1/2=0.

7)若d(v)=2,則由引理1知，v至少和兩個5+-點相鄰.從而，根據R1,w′(v)≥6×2-19+2×7/2=0.