次立方平面圖的單射邊染色

李艷怡，陳莉莉

(華僑大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，福建 泉州 362021)

1 預(yù)備知識

平面圖是一類重要的特殊圖，關(guān)于平面圖的單射點染色已經(jīng)得到較多結(jié)果.文獻[4-6]研究了平面圖的單射點色數(shù)與最大度、圍長之間的關(guān)系及圍長至少為7，5時平面圖的單射點色數(shù)；Dong等[7]在圍長為6的條件下研究平面圖的單射點色數(shù)；朱海洋等[8]考慮最大度Δ(G)≤6且不含4，5，6，7-圈的平面圖的單射點色數(shù)的上界.除此之外，學(xué)者們還考慮了平面圖的單射可選性，即對圖G的每個點v分配一個列表L(v)，要求單射染色f需滿足f(v)∈L(v)，這樣的染色稱為列表單射染色.文獻[9-12]在圍長限制下研究平面圖的列表單射色數(shù)的界；Brimkov 等[13]考慮了圍長為6的次立方平面圖的單射可選性；卜月華等[14]考慮了5--圈和 5--圈不交的平面圖的列表單射染色.對于單射邊染色，Bu等[15]在限制最大度及最大平均度條件下，給出了稀疏圖單射邊色數(shù)的上界；卜月華等[16]研究了圍長至少為6且6-圈與7--圈不相交的平面圖G的單射邊色數(shù).

討論簡單次立方平面圖的單射邊色數(shù).設(shè)G=(V，E)是簡單平面圖，Δ=Δ(G)為G的最大度，如果Δ(G)≤3，則稱G是次立方圖.圍長g表示G中最短圈的長度.得到以下2個定理.

使用權(quán)轉(zhuǎn)移的方法進行定理的證明.權(quán)轉(zhuǎn)移的主要思想是對圖G的點和面進行賦權(quán)，使得初始權(quán)值之和為負數(shù).研究圖內(nèi)部的結(jié)構(gòu)性質(zhì)并且給定權(quán)轉(zhuǎn)移規(guī)則，進行點點之間，面面之間及點面之間的權(quán)值轉(zhuǎn)移，最終得到新的權(quán)值之和為非負數(shù).由于權(quán)轉(zhuǎn)移過程是在圖內(nèi)部進行的，所以總權(quán)值應(yīng)當不會變化，這就導(dǎo)出了矛盾.

在下面的證明中，對于圖G的一個染色f，任意e∈E(G)，用F(e)表示在染色過程中邊e不能使用的顏色集合.

2 定理1的證明

引理1圖G不存在1度點.

證明：假設(shè)圖G存在1度點u，v是它唯一的鄰點.令G′=G-u，由G的極小性，存在G′的用6種顏色的單射邊染色f′.因為|F(uv)|≤4，所以令f(uv)∈CF(uv)，而對e∈E(G){uv}，有f(e)=f′(e).這樣就得到G的用6種顏色的單射邊染色f，與假設(shè)矛盾.

引理2圖G中2度點只能和3度點相鄰.

證明：假設(shè)u，v是G中2個相鄰的2度點，w是v的另一個鄰點.令G′=G-v，由G的極小性，存在G′的用6種顏色的單射邊染色f′.因為|F(uv)|≤4，|F(vw)|≤5，所以可以先對邊vw染色，再對邊uv染色，此外，對于e∈E(G){uv，vw}，有f(e)=f′(e).這樣就得到G的用6種顏色的單射邊染色f，與假設(shè)矛盾.

引理3G中3度點最多和1個2度點相鄰.

證明：假設(shè)u是G中1個3度點，u與2個2度點v和w相鄰，u的另一個鄰點為u1，w的另一個鄰點為w1.令G′=G-u，由G的極小性，存在G′的用6種顏色的單射邊染色f′.刪去邊ww1上的顏色，此時，|F(uv)|≤4，|F(uw)|≤5，|F(uu1)|≤5，|F(ww1)|≤4，所以先對邊uu1進行染色，再染邊ww1，最后分別對邊uv，uw進行染色.此外，對于e∈E(G){uv，uw，uu1，ww1}，有f(e)=f′(e).這樣就得到G的用6種顏色的單射邊染色f，與假設(shè)矛盾.

根據(jù)平面圖的歐拉公式

V-E+F=2，

以及握手定理

可以得到

分別對圖G的頂點和面進行初始賦權(quán)，?v∈V(G)，令ω(v)=2d(v)-6，?f∈F(G)，則令ω(f)=d(f)-6，那么可以得到初始總權(quán)值為

給定權(quán)轉(zhuǎn)移規(guī)則R：每個面給該面上的每個2度點權(quán)值1.

如果v是2度點，則初始權(quán)值ω(v)=-2.因為2度點存在2個面上，且從每一個面得到1的權(quán)值，所以得到新的權(quán)值ω′(v)=-2+1+1=0.

如果v是3度點，則初始權(quán)值ω(v)=0.由于3度點沒有進行權(quán)轉(zhuǎn)移，所以新權(quán)值ω′(v)=0.

由于g≥8，即d(f)≥8，所以ω′(f)≥0恒成立.

由于權(quán)轉(zhuǎn)移是在圖內(nèi)部進行，所以總權(quán)值不會變化，也就是

出現(xiàn)矛盾，所以極小反例G不存在，定理1得證.

3 定理2的證明

引理5圖G不存在1度點.

證明：假設(shè)G中存在1度點u，v是它唯一的鄰點.令G′=G-u，由G的極小性，存在G′的用7種顏色的單射邊染色f′.因為|F(uv)|≤4，所以令f(uv)∈CF(uv)，而對e∈E(G){uv}，f(e)=f′(e).這樣得到G的用7種顏色的單射邊染色f，與假設(shè)矛盾.

引理6圖G不存在2度點.

證明：假設(shè)u是G中的2度點，w和v是它的兩個鄰點，令G′=G-u，由G的極小性，存在G′的用7種顏色的單射邊染色f′.因為|F(uv)|≤6，|F(uw)|≤6，且邊uw和uv可以染相同的顏色，因此，可以得到G的用7種顏色的單射邊染色f，與假設(shè)矛盾.

給定點的初始權(quán)值為?v∈V(G)，ω(v)=2d(v)-6，面的初始權(quán)值為?f∈F(G)，ω(f)=d(f)-6，根據(jù)歐拉公式，初始總權(quán)值為

根據(jù)以上所得性質(zhì)，G中只存在3度點，因此，所有點的總權(quán)值為

對于面，由于g≥6，即d(f)≥6，所以得到所有面的總權(quán)值為

最終可以得到

出現(xiàn)矛盾，也就是極小反例G不存在，定理2得證.

4 結(jié)束語

通過極小反例及權(quán)轉(zhuǎn)移的方法，研究次立方平面圖的結(jié)構(gòu)性質(zhì)，最終得到其在限制圍長條件下的單射邊色數(shù)的上界.