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

胡黎莉

（閩南師范大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院,福建漳州 363000）

僅考慮有限簡(jiǎn)單圖.沿用文獻(xiàn)[1]的記號(hào)，除非另有說明.

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

證明了以下結(jié)果.

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

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

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

1 預(yù)備知識(shí)和引理

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

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

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

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

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

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

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

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

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

引理4G中的每個(gè)5--點(diǎn)至少和一個(gè)6+-點(diǎn)相鄰.

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

引理5G中的6-度點(diǎn)不能和6個(gè)輕-點(diǎn)相鄰.

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

引理6G中的兩個(gè)壞-點(diǎn)不能相鄰.

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

引理7假設(shè)d(v)=5且v有3個(gè)2-鄰點(diǎn)，則：

1)如果v有一個(gè)3-鄰點(diǎn)，則v不能和壞的6-度點(diǎn)相鄰.

2)v不能和兩個(gè)壞的6-度點(diǎn)相鄰.

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

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

引理8假設(shè)d(v)=6且v有4個(gè)2-鄰點(diǎn)，則：

1)v不能和兩個(gè)壞的5-度點(diǎn)相鄰.

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

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

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

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

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

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

2 定理1的證明

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

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

R1.G的每個(gè)5+-點(diǎn)向其每個(gè)2-鄰點(diǎn)轉(zhuǎn)移權(quán)值7/2.

R2.G的每個(gè)4+-點(diǎn)向其每個(gè)3-鄰點(diǎn)轉(zhuǎn)移權(quán)值1/2.

R3.G的每個(gè)6+-點(diǎn)向其每個(gè)相鄰的壞5-度點(diǎn)轉(zhuǎn)移權(quán)值3.

R4.G的每個(gè)5+-點(diǎn)向其每個(gè)相鄰的壞6-度點(diǎn)轉(zhuǎn)移權(quán)值1/2.

為了方便起見，記v的2-鄰點(diǎn)的個(gè)數(shù)為t.下面分7種情況討論：

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

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

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

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

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

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

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