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

王 侃

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

0 引言

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

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

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

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

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

本文考慮對(duì)平面圖類改進(jìn)上述部分結(jié)論，得到如下的結(jié)果:

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

1 基本概念

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

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

2 極小反例的性質(zhì)

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

斷言1 δ(G)≥5．

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

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

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

假設(shè) G 包含一個(gè) 4-點(diǎn) v，且 v1，v2，v3，v4是 v的鄰點(diǎn)，則 H=G-v+{v1v2，v3v4}(若 v1v2或 v3v4不存在)(見圖1)．由G的極小性知H有一個(gè)線性染色c應(yīng)用顏色集合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 對(duì)頂點(diǎn)染相同的顏色．

不失一般性，設(shè) 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的禁用顏色數(shù)最多為12，于是可用C中的顏色染好v．

3)v1，v2，v3，v4有 2 對(duì)頂點(diǎn)染相同的顏色．

不失一般性，設(shè) 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的禁用顏色數(shù)最多為12，于是可用C中的顏色染好v．?dāng)嘌?證畢．

斷言2 不存在壞5-點(diǎn)．

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

圖1 斷言1中的子結(jié)構(gòu)

圖2 斷言2中的子結(jié)構(gòu)

由G的極小性知H有一個(gè)線性染色c應(yīng)用顏色集合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 個(gè)頂點(diǎn)染相同顏色．考慮下面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 的禁用顏色數(shù)最多為12，于是可用C中的顏色染好v．

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

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

不失一般性，設(shè) 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的禁用顏色數(shù)至多為12，于是可用C中的顏色染好v．

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

不失一般性，設(shè) 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的禁用顏色數(shù)至多為12，于是可用C中的顏色染好v．?dāng)嘌?證畢．

3 定理1的證明

設(shè)G是定理1的一個(gè)極小反例，為完成證明，應(yīng)用權(quán)轉(zhuǎn)移方法．首先，結(jié)合歐拉公式|V(G)|-

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

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

權(quán)轉(zhuǎn)移規(guī)則如下:

［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］．浙江師范大學(xué)學(xué)報(bào):自然科學(xué)版，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．