李艷怡，陳莉莉

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

1 預(yù)備知識(shí)

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

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

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

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

2 定理1的證明

引理1圖G不存在1度點(diǎn).

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

引理2圖G中2度點(diǎn)只能和3度點(diǎn)相鄰.

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

引理3G中3度點(diǎn)最多和1個(gè)2度點(diǎn)相鄰.

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

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

V-E+F=2，

以及握手定理

可以得到

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

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

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

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

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

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

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

3 定理2的證明

引理5圖G不存在1度點(diǎn).

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

引理6圖G不存在2度點(diǎn).

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

給定點(diǎn)的初始權(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度點(diǎn)，因此，所有點(diǎn)的總權(quán)值為

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

最終可以得到

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

4 結(jié)束語(yǔ)

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