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

姚瀟彥

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

0 引言

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

圖G的一個k-邊染色是一個映射φ:E(G)→{1，2，…，k}，其中k是整數．若映射φ還滿足對于G中的每一對相鄰邊e和e'，有φ(e)≠φ(e')，則稱這個k-邊染色是正常的;若G有一個正常的k-邊染色，則稱G是k-邊可染的;G的邊色數χ'(G)是使得G是k-邊可染的最小的整數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的邊列表色數χ'l(G)是使得G是k-邊可選擇的最小的整數k．類似地，可定義同時染頂點和邊的G的全列表色數χ"l(G)．由定義可直接得到χ'l(G)≥χ'(G)≥Δ(G)和 χ"l(G)≥χ"(G)≥Δ(G)+1．

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

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

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

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

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

1 引理

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

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

引理1 G是連通的．

引理2 設?e=uv∈E．若6+-點相鄰，3-點只與 5+-點相鄰．

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

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

引理4 令G'是G中所有關聯2-點的邊導出的子圖，則G'是一個森林．

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

引理5 G具有以下性質:

2)每個關聯3-面的面是5-面或8+-面;

3)若一個2-點關聯一個3-面，則它關聯的另一個面是6-面或9+-面;

4)若一個3-點關聯一個3-面和一個5-面，則它關聯的另一個面是8+-面;

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

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

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

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

①d(u2)≥3，d(u3)≥3．因為G不含4-圈，所以f2不可能是3-面或4-面．事實上，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-面，則會產生一個 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-面，則會產生一個4-圈 C=［vu2u1u4v］;若 f2=［vu2u1x1u4u3v］是6-面，則會產生一個4-圈 C=［vu1x1u4v］．綜上所述，f2是8+-面．引理5證畢．

2 定理1的證明

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

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

權轉移規則如圖1所示．

R3:每個5+-點與其關聯的3-面各

R4:每個5+-面向每個關聯的點轉

圖1 權轉移規則圖

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

先考察面的新權．

因為G是簡單圖，所以對每個面f都有d(f)≥3．又由權轉移規則知:若d(f)≥4，則ch'(f)≥0．所以，下面只需驗證3-面．

設f為3-面，則ch(x)=-1，由引理2知，f至多關聯1個3--點．

若f關聯一個3--點，則由引理2知，其余2個均為5+-點，由R3知0．

設v為3-點，則ch(v)=-1，由引理5的1)知，f至多關聯1個3-面．

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

其次考察點的新權．

設 v為 2-點，則 ch(v)=-2．

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

設v為4-點，則ch'(v)=0，由引理5的1)知，v至多關聯2個3-面．又由權轉移規則知，v只向3-面轉權．所以，當v關聯2個3-面時 ch'(v)最少．由引理5的5)知，v還關聯2個8+-面，所以 ch'(v)≥

設t是v關聯的3-面的個數．稱關聯3-面的3-點為壞3-點．用b3(v)表示v相鄰的壞3-點的個數．

設v為5-點，則ch'(v)=1，由權轉移規則知，v只向3-面和3-點轉權，由引理5的1)知，v至多關聯2 個3-面．

1)t=0，此時v只向3-點轉權，且至多與5個壞3-點相鄰，則

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

設v為6-點，則ch(v)=2．下面將根據v與2-點相鄰的情形對6-點的新權逐一進行驗證．

1)v是一個2-點 u的 master．

①v不與三角形關聯，那么v至多關聯2個3-面．

②v與三角形關聯，由于G不含4-圈，故v至多關聯3個3-面．

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

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

t=3，此時v不需要向3-點轉權，由引理5的5)知，v至少關聯3個8+-面，從而

2)v不是任意2-點的master，此時v至多與3個3-面關聯．

①t=0，此時v只向3-點轉權，且至多與6個壞3-點相鄰，因此

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

至此，對?x∈V∪F，ch'(x)≥0都已得到驗證．定理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．