最大度為6的平面圖是13-線性可染的*

王 侃

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

0 引言

本文所考慮的圖都是簡單圖．用V(G)，E(G)，Δ(G)和δ(G)分別表示圖G的頂點集、邊集、最大度和最小度．G的圍長g(G)是指G中最短圈的長度．

圖G的一個正常染色是從頂點集合V(G)到顏色集合{1，2，…，k}的一個映射，使得任意2個相鄰的頂點染不同的顏色;圖G的一個線性k-染色是一個正常染色，使得染任意2種顏色的頂點集合導出的子圖是一些點不交的路的并;圖G的線性色數lc(G)定義為G的所有線性k-染色中最小的k值．

Yuster［1］首先研究了圖的線性染色問題，證明了任意圖G的線性色數滿構造了一類圖使 實上，這個概念是圖的無圈染色的一種特殊情形．圖G的一個無圈染色是G的一個正常染色，使得染任意2種顏色的頂點集合導出的子圖是一個森林．無圈染色的概念是由Grünbaum［2］提出的，這方面的研究可參閱文獻［2-5］．

2008年，Esperet等［6］把線性染色的概念推廣到線性選擇性上，研究了樹、格子圖、完全二部圖、平面圖、外平面圖、最大度為3或4的圖以及有較小最大平均度的圖的線性選擇數．文獻［6］蘊含了以下結果:若圖G滿足最大度Δ(G)≤3，則lc(G)≤5;對平面圖 G，若 g(G)≥16且Δ(G)≥3，則lc(G)=

文獻［7］證明了:對一個平面圖 G，若存在一個有序對(Δ，g)∈{(13，7)，(7，9)，(5，11)，(3，13)}Δ(G)≤5，則 lc(G)≤14;對平面圖 G，若 Δ(G)≥52，則

本文考慮對平面圖類改進上述部分結論，得到如下的結果:

定理1 若G是平面圖且滿足Δ(G)≤6，則lc(G)≤13．

1 基本概念

對于一個平面圖G，用F(G)表示它的面集合．對任意的 f∈F(G)，若u1，u2，…，un是 f邊界上依序排列的頂點，則記 f=［u1u2… un］，且點的重復出現是允許的;面的度是指它的邊界上邊的條數，其中割邊被計算2次;對于任意的x∈V(G)∪F(G)，用dG(x)表示G中x的度，在不產生混淆的情況下，可以用d(x)代替dG(x);一個度數為k的頂點(面)被稱為k-點(k-面);一個度數至少為k或至多為k的頂點(面)被稱為k+-點(k+-面)或k--點(k--面);用NG(v)表示G中v的鄰點的集合．

設c是G的一個部分線性染色，顏色集合為C．對于任意的v∈V(G)，用C2(v)表示C中正好在NG(v)上出現2次的顏色子集合;對于任意的頂點集合T，用C*2(T)表示C中至少在T上出現2次的顏色子集合．為討論方便，稱至少關聯4個3-面的5-點為壞5-點．

2 極小反例的性質

假設定理1不成立．設G是一個極小反例，即G是一個平面圖，滿足Δ(G)≤6且lc(G)＞13，但對于任意的一個階數更小的平面圖H，滿足Δ(H)≤6，有lc(H)≤13．設C={1，2，…，13}表示被應用的顏色集合．容易看到G是連通的，且G具有以下性質:

斷言1 δ(G)≥5．

證明 假設G包含1-點v與某點u相鄰．令H=G-v，則H是一個平面圖，滿足Δ(H)≤Δ(G)≤6．由G的極小性知，H有一個線性染色c應用顏色集合C．為將c擴充到整個圖G，用不在C2(u)∪所以總有1種顏色可以染給v．與G的選擇矛盾!

假設G包含一個2-點v，其鄰點為x，y，則由G的極小性知H=G-v有一個線性染色c應用顏色集合C．用不在{c(x)，c(y)}∪C*2(NH(x)∪NH(y))中的顏色染v，v的禁用顏色數最多為Δ(G)+1=7，于是可用C中的顏色染好v．與G的選擇矛盾!

假設G包含一個3-點v，其鄰點為x，y，z，則由G的極小性知H=G-v+{xy}(若xy不存在)有一個線性染色c應用顏色集合C．用不在{c(x)，c(y)，c(z)}∪C*2((NG(x)∪NG(y)∪NG(z)){v})中的顏色染v，v的禁用顏色數最多為10，于是可用C中的顏色染好v．與G的選擇矛盾!

假設 G 包含一個 4-點 v，且 v1，v2，v3，v4是 v的鄰點，則 H=G-v+{v1v2，v3v4}(若 v1v2或 v3v4不存在)(見圖1)．由G的極小性知H有一個線性染色c應用顏色集合C．顯然，c(v1)≠c(v2)且c(v3)≠c(v4)，考慮3種情形染 v．

1)v1，v2，v3，v4染互不相同的顏色．

用不在{c(v1)，c(v2)，c(v3)，c(v4)}∪ C*2(NG(v1){v})∪C*2(NG(v2){v})∪C*2(NG(v3){v})∪C*2(NG(v4){v})中的中的顏色染好v．

2)v1，v2，v3，v4恰有 1 對頂點染相同的顏色．

不失一般性，設 c(v1)=c(v4)．用不在{c(v1)，c(v2)，c(v3)}∪C*2(NG(v1)∪NG(v4){v})∪C*2(NG(v2){v})∪C*2(NG(v3){v})中的顏色染v，v的禁用顏色數最多為12，于是可用C中的顏色染好v．

3)v1，v2，v3，v4有 2 對頂點染相同的顏色．

不失一般性，設 c(v1)=c(v4)且 c(v2)=c(v3)．用不在{c(v1)，c(v2)}∪C*2(NG(v1)∪NG(v4){v})∪C*2(NG(v2)∪NG(v3){v})中的顏色染v，v的禁用顏色數最多為12，于是可用C中的顏色染好v．斷言1證畢．

斷言2 不存在壞5-點．

證明 假設G有一個壞5-點v，則v至少和4個3-面關聯．設vi(i=1，2，3，4，5)是v的鄰點，fi是和v關聯的面．設 f1=［v1vv2］，f2=［v2vv3］，f3=［v3vv4］，f4=［v4vv5］．H=G-v+{v2v4，v1v5}(若 v2v4或v1v5不存在)，如圖2所示．

圖1 斷言1中的子結構

圖2 斷言2中的子結構

由G的極小性知H有一個線性染色c應用顏色集合C．易見c(v1)≠c(v2)，c(v1)≠c(v5)，c(v4)≠c(v5)，且 c(v2)，c(v3)，c(v4)互不相同．于是在{v1，v2，v3，v4，v5}中至多有 2 個頂點染相同顏色．考慮下面2種情形:

1)c(v1)，c(v2)，c(v3)，c(v4)，c(v5)互不相同．

用不在{c(v1)，c(v2)，c(v3)，c(v4)，c(v5)}，C*2(NG(v1){v，v2})，C*2(NG(v2){v，v1，v3})，C*2(NG(v3){v，v2，v4})，C*2(NG(v4){v，v3，v5})，C*2(NG(v5){v，v4})中的顏色染 v，v 的禁用顏色數最多為12，于是可用C中的顏色染好v．

2)c(v1)，c(v2)，c(v3)，c(v4)，c(v5)中有相同顏色．考慮下面2 種子情形:

①c(v1)=c(v4)或c(v2)=c(v5)．

不失一般性，設 c(v1)=c(v4)．用不在{c(v1)，c(v2)，c(v3)，c(v5)}，C*2((NG(v2){v，v1，v3})∪(NG(v3){v，v2，v4})∪(NG(v5){v，v4}))和 C*2((NG(v1){v，v2})∪(NG(v4){v，v3，v5}))中的顏色染v，v的禁用顏色數至多為12，于是可用C中的顏色染好v．

②c(v1)=c(v3)或c(v3)=c(v5)．

不失一般性，設 c(v1)=c(v3)．用不在{c(v1)，c(v2)，c(v4)，c(v5)}，C*2((NG(v2){v，v1，v3})∪(NG(v4){v，v3，v5})∪(NG(v5){v，v4}))和 C*2((NG(v1){v，v2})∪(NG(v3){v，v2，v4}))中的顏色染v，v的禁用顏色數至多為12，于是可用C中的顏色染好v．斷言2證畢．

3 定理1的證明

設G是定理1的一個極小反例，為完成證明，應用權轉移方法．首先，結合歐拉公式|V(G)|-

定義初始權函數w:對v∈V(G)，令 w(v)=d(v)-6;對 f∈F(G)，令 w(f)=2d(f)-6．由式(1)得總的權和為-12．然后定義一個權轉移規則并且在所有的點和面上執行它．一旦權轉移結束，就會產生一個新的權函數w'．在整個權轉移過程中權和是不變的，但是對于所有的x∈V(G)∪F(G)，有w'(x)≥0．這就導致了下面一個很明顯的矛盾:

因此，這樣的反例G是不存在的．

權轉移規則如下:

［1］Yuster R．Linear coloring of graphs［J］．Discrete Math，1998，185(1/2/3):293-297．

［2］Grünbaum B．Acyclic colorings of planar graphs［J］．Israel J Math，1973，14(4):390-408．

［3］Borodin O V．On acyclic colorings of planar graphs［J］．Discrete Math，1979，25(3):211-236．

［4］Kostochka A V．Acyclic 6-coloring of planar graphs［J］．Metody Diskret Anal，1976，28:40-56．

［5］Wang Weifan，Shu Qiaojun，Wang Kan，et al．Acyclic chromatic indices of planar graphs with large girth［J］．Discrete Appl Math，2011，159(12):1239-1253．

［6］Esperet L，Montassier M，Raspaud A．Linear choosability of graphs［J］．Discrete Math，2008，308(17):3938-3950．

［7］Raspaud A，Wang Weifan．Linear coloring of planar graphs with large girth［J］．Discrete Math，2009，309(18):5678-5686．

［8］王侃．不含3-圈平面圖的線性染色［J］．浙江師范大學學報:自然科學版，2011，34(2):135-140．

［9］Li Chao，Wang Weifan，Raspaud A．Upper bounds on the linear chromatic number of graph［J］．Discrete Math，2011，311(4):232-238．