最大度為6且不含4-圈和7-圈的平面圖的邊列表和全列表*

姚瀟彥

(浙江師范大學(xué)數(shù)理與信息工程學(xué)院，浙江金華 321004)

0 引言

本文考慮的圖都是簡單、有限的無向圖．文中未加定義的術(shù)語和記號參閱文獻(xiàn)［1］．用V(G)，E(G)，F(xiàn)(G)，Δ(G)和δ(G)分別表示平面圖G的頂點(diǎn)集、邊集、面集、最大度和最小度(在不引起混淆的情況下簡記為 V，E，F(xiàn)，Δ 和 δ)．

圖G的一個k-邊染色是一個映射φ:E(G)→{1，2，…，k}，其中k是整數(shù)．若映射φ還滿足對于G中的每一對相鄰邊e和e'，有φ(e)≠φ(e')，則稱這個k-邊染色是正常的;若G有一個正常的k-邊染色，則稱G是k-邊可染的;G的邊色數(shù)χ'(G)是使得G是k-邊可染的最小的整數(shù)k;稱映射L為圖G的一個邊列表，如果它給每條邊e∈G一個顏色集合L(e);若有一個正常的邊染色φ，使得每一條邊e滿足φ(e)∈L(e)，則稱G是L-邊可染的，或稱φ是G的一個L邊染色;若對任意表L和每條邊e∈E(G)，都有|L(e)|≥k，且G是L邊可染的，則稱G是k-邊可選的．G的邊列表色數(shù)χ'l(G)是使得G是k-邊可選擇的最小的整數(shù)k．類似地，可定義同時染頂點(diǎn)和邊的G的全列表色數(shù)χ"l(G)．由定義可直接得到χ'l(G)≥χ'(G)≥Δ(G)和 χ"l(G)≥χ"(G)≥Δ(G)+1．

下面是著名的邊列表染色和全列表染色猜想:

猜想1 如果G是一個多重圖，則:1)χ'l(G)= χ'(G);2)χ"l(G)= χ"(G)．

對于二部重圖、奇階完全圖、多重圈、外平面圖，已證明猜想1的1)成立．文獻(xiàn)［2］證明了對于Δ≥12可嵌入非負(fù)特征曲面上的圖，猜想1成立;文獻(xiàn)［3］證明了對于最大度至少為7且不含4-圈的平面圖及最大度至少為6且不含4-圈和6-圈的平面圖，猜想1成立．

本文研究Δ≥6的平面圖的邊列表染色和全列表染色問題，得到以下結(jié)果:

定理1 若G是Δ≥6且沒有4-圈和7-圈的平面圖，則G是6-邊可選的和7-全可選的．

1 引理

方便起見，先引進(jìn)一些定義和記號．把度為k或度不小于k或度不大于k的點(diǎn)(或面)分別稱做k-點(diǎn)(面)，k+-點(diǎn)(面)，k--點(diǎn)(面);一個面f的度d(f)，是指關(guān)聯(lián)f的邊的條數(shù)，其中割邊被計算2次．用nv(f)表示任意一個關(guān)聯(lián)f的點(diǎn)v經(jīng)過f的閉途徑的次數(shù)．

假設(shè)定理1不成立，并設(shè)G是定理1的一個使σ(G)=|V|+|E|最小的反例，即G本身不是6-邊可選的和7-全可選的，但它的每個真子圖都是6-邊可選的和7-全可選的，則G有以下幾個性質(zhì):

引理1 G是連通的．

引理2 設(shè)?e=uv∈E．若6+-點(diǎn)相鄰，3-點(diǎn)只與 5+-點(diǎn)相鄰．

引理3 G不含2-交替圈．

由G的極小性容易證明引理1，引理2和引理3的證明可參閱文獻(xiàn)［4］．

引理4 令G'是G中所有關(guān)聯(lián)2-點(diǎn)的邊導(dǎo)出的子圖，則G'是一個森林．

設(shè)T是G'中的一棵極大樹，由引理2知，T的所有葉子都是6+-點(diǎn)，由歸納法容易證明G'中存在一個飽和所有2-點(diǎn)的匹配M．如果給每個極大樹配一個極大匹配，并設(shè)v是G中任意一個2-點(diǎn)，那么稱v的被匹配飽和的鄰點(diǎn)為v的master．

引理5 G具有以下性質(zhì):

2)每個關(guān)聯(lián)3-面的面是5-面或8+-面;

3)若一個2-點(diǎn)關(guān)聯(lián)一個3-面，則它關(guān)聯(lián)的另一個面是6-面或9+-面;

4)若一個3-點(diǎn)關(guān)聯(lián)一個3-面和一個5-面，則它關(guān)聯(lián)的另一個面是8+-面;

5)設(shè) f1，f2，f3是v關(guān)聯(lián)的面，且依順時針方向排列，如果f1，f3都是3-面，那么 f2是8+-面．

證明:1)，2)和3)易證，下證4)和5)．

4)設(shè)v是一個3-點(diǎn)，f1，f2，f3是v關(guān)聯(lián)的3個面，不失一般性，假設(shè)它們是依順時針方向排列的，且d(f1)≤d(f2)，其中 f1是 5-面，f3是 3-面．用反證法．設(shè) d(f1)=d(f2)=5，且 f1=［vuu1u2u3］，f2=［vuv1v2v3］，若 f1和 f2正常相鄰，則會產(chǎn)生一個 7-圈 C=［uu1u2u3v3v2v1u］．事實(shí)上，{u1，u2，u3}∩{v1，v2，v3}=?．否則，若 u1=v1，則 u 是一個 2-點(diǎn)，與引理 2 矛盾;若 u2=v1，則會產(chǎn)生一個 4-圈 C=［v1(=u2)u3vuv1］;若u3=v1，則會產(chǎn)生一個 4-圈 C=［v1(=u3)u2u1uv1］．所以 v1≠u1(u2，u3)．類似地可驗(yàn)證v2≠u1(u2，u3)，v3≠u1(u2，u3)．所以，f1和f2不可能正常相鄰，但 f1和 f2也不可能非正常相鄰．不然，u是一個2-點(diǎn)，與引理2矛盾．若d(f2)=6，可類似證明會產(chǎn)生4-圈或7-圈，得到矛盾．所以，若d(f1)=5，則由 d(f1)≤d(f2)可得 d(f2)≥8．

5)設(shè)v是f1，f2，f3的公共點(diǎn)，u1，u2和u3，u4分別是f1和f3關(guān)聯(lián)的另外2個頂點(diǎn)，且按順時針方向排列．對u2，u3分3種情形討論:

①d(u2)≥3，d(u3)≥3．因?yàn)镚不含4-圈，所以f2不可能是3-面或4-面．事實(shí)上，G也不是5-面或6-面．否則，若 f2=［vu2x1x2u3v］是 5-面，則 C=［vu1u2x1x2u3u4v］是 7-圈;若 f2=［vu2x1x2x3u3v］是 6-面，則C=［vu2x1x2x3u3u4v］是7-圈．但 G 不含7-圈，所以 f2是 8+-面．

②d(u3)≥3，d(u2)=2，或 d(u2)≥3，d(u3)=2．由對稱性，不妨考慮 d(u2)≥3，d(u3)=2．由引理4的2)知，f2一定是 5+-面．若 f2=［vu2x1u4u3v］是 5-面，則會產(chǎn)生一個 4-圈 C=［vu2x1u4v］;若 f2=［vu2x1x2u4u3v］是 6-面，由于 G 不含4-圈，所以 u1≠x1且 u1≠x2，則 C=［vu1u2x1x2u4u3v］是7-圈．但 G 不含7-圈，所以 f2是8+-面．

③d(u2)=d(u3)=2．由引理4的2)知，f2一定是5+-面．若 f2=［vu2u1x1u4u3v］是5-面，則會產(chǎn)生一個4-圈 C=［vu2u1u4v］;若 f2=［vu2u1x1u4u3v］是6-面，則會產(chǎn)生一個4-圈 C=［vu1x1u4v］．綜上所述，f2是8+-面．引理5證畢．

2 定理1的證明

設(shè)G是定理1的一個使σ(G)=|V|+|E|最小的反例．以下將運(yùn)用Discharging方法導(dǎo)出完成定理1證明所需要的矛盾．首先，給G的任意的x∈V∪F分配初始權(quán)ch(x)=d(x)－4，由平面圖的歐拉

以下將定義一個權(quán)轉(zhuǎn)移規(guī)則，重新分配點(diǎn)和面的權(quán)，并設(shè)ch'(x)是重新分配點(diǎn)和面的權(quán)后元素x∈V∪F的新權(quán)．將要證明對每個 x∈V∪F都有一方面，由于權(quán)的轉(zhuǎn)移只是在同一個圖的點(diǎn)和面之間進(jìn)行，權(quán)的總和應(yīng)該保持不變，因此得到-8≥0，即得到了證明定理1所需要的矛盾．

權(quán)轉(zhuǎn)移規(guī)則如圖1所示．

R3:每個5+-點(diǎn)與其關(guān)聯(lián)的3-面各

R4:每個5+-面向每個關(guān)聯(lián)的點(diǎn)轉(zhuǎn)

圖1 權(quán)轉(zhuǎn)移規(guī)則圖

下面只需驗(yàn)證對于每個x∈V∪F都有ch'(x)≥0．

先考察面的新權(quán)．

因?yàn)镚是簡單圖，所以對每個面f都有d(f)≥3．又由權(quán)轉(zhuǎn)移規(guī)則知:若d(f)≥4，則ch'(f)≥0．所以，下面只需驗(yàn)證3-面．

設(shè)f為3-面，則ch(x)=-1，由引理2知，f至多關(guān)聯(lián)1個3--點(diǎn)．

若f關(guān)聯(lián)一個3--點(diǎn)，則由引理2知，其余2個均為5+-點(diǎn)，由R3知0．

設(shè)v為3-點(diǎn)，則ch(v)=-1，由引理5的1)知，f至多關(guān)聯(lián)1個3-面．

若v關(guān)聯(lián)1個3-面，則由引理4的2)和引理4的4)知，v關(guān)聯(lián)的另2個面要么是5-面和8+-面，要

其次考察點(diǎn)的新權(quán)．

設(shè) v為 2-點(diǎn)，則 ch(v)=-2．

若v關(guān)聯(lián)一個3-面，則由引理5的3)知，v關(guān)聯(lián)的另一個面是6+-面，由R1和 R4知，ch'(v)=

設(shè)v為4-點(diǎn)，則ch'(v)=0，由引理5的1)知，v至多關(guān)聯(lián)2個3-面．又由權(quán)轉(zhuǎn)移規(guī)則知，v只向3-面轉(zhuǎn)權(quán)．所以，當(dāng)v關(guān)聯(lián)2個3-面時 ch'(v)最少．由引理5的5)知，v還關(guān)聯(lián)2個8+-面，所以 ch'(v)≥

設(shè)t是v關(guān)聯(lián)的3-面的個數(shù)．稱關(guān)聯(lián)3-面的3-點(diǎn)為壞3-點(diǎn)．用b3(v)表示v相鄰的壞3-點(diǎn)的個數(shù)．

設(shè)v為5-點(diǎn)，則ch'(v)=1，由權(quán)轉(zhuǎn)移規(guī)則知，v只向3-面和3-點(diǎn)轉(zhuǎn)權(quán)，由引理5的1)知，v至多關(guān)聯(lián)2 個3-面．

1)t=0，此時v只向3-點(diǎn)轉(zhuǎn)權(quán)，且至多與5個壞3-點(diǎn)相鄰，則

3)t=2，此時v至多與1個壞3-點(diǎn)相鄰，由引理5的5)知，v至少關(guān)聯(lián)1個8+-面，則ch'(v)≥1-

設(shè)v為6-點(diǎn)，則ch(v)=2．下面將根據(jù)v與2-點(diǎn)相鄰的情形對6-點(diǎn)的新權(quán)逐一進(jìn)行驗(yàn)證．

1)v是一個2-點(diǎn) u的 master．

①v不與三角形關(guān)聯(lián)，那么v至多關(guān)聯(lián)2個3-面．

②v與三角形關(guān)聯(lián)，由于G不含4-圈，故v至多關(guān)聯(lián)3個3-面．

t=1，此時v至多與4個壞3-點(diǎn)相鄰．若b3(v)=0，則v只向正常3-點(diǎn)轉(zhuǎn)權(quán)，且至多與4個壞3-點(diǎn)相b3(v)=2，則v至少關(guān)聯(lián)1個8+-面和1個6+-面，此時v至多與2個正常3-點(diǎn)相鄰，從而ch'(v)≥2-1個正常3-點(diǎn)相鄰，從而少關(guān)聯(lián)3個8+-面，此時v不與正常3-點(diǎn)相鄰，從而

t=2，此時v至多與2個壞3-點(diǎn)相鄰．若 b3(v)=0，則由引理5知，v至少關(guān)聯(lián)1個6+-面，從而;若b3(v)=1，則由引理5知，v至少關(guān)聯(lián)1個8+-面，此時v至多與1個正常3-點(diǎn)相鄰，從而至少關(guān)聯(lián)2個8+-面，從而

t=3，此時v不需要向3-點(diǎn)轉(zhuǎn)權(quán)，由引理5的5)知，v至少關(guān)聯(lián)3個8+-面，從而

2)v不是任意2-點(diǎn)的master，此時v至多與3個3-面關(guān)聯(lián)．

①t=0，此時v只向3-點(diǎn)轉(zhuǎn)權(quán)，且至多與6個壞3-點(diǎn)相鄰，因此

④t=3，此時v不向任何3-點(diǎn)轉(zhuǎn)權(quán)，且由引理5的4)知，v至少關(guān)聯(lián)3個8+-面，因此ch'(v)≥2-

至此，對?x∈V∪F，ch'(x)≥0都已得到驗(yàn)證．定理1得證．

［1］Bondy J A，Murty U S R．Graph theory［M］．Berlin:Springer，2008．

［2］Borodin O V，Kostochka A V，Woodall D R．List edge and list total colorings of multigraphs［J］．J Combin Theory，1997，71(2):184-204．

［3］Liu Bin，Hou Jianfeng，Liu Guizhen．List edge and list total colorings of planar graphs without short cycles［J］．Information Processing Letters，2008，108(6):347-351．

［4］Wang W F，Lih K W．Structural properties and edge choosability of planar graphs without 6-cycles［J］．Combin Probab Comput，2001，10(3):267-276．