稀疏圖的k-frugal列表染色

房啟明，張 莉

（同濟(jì)大學(xué)數(shù)學(xué)科學(xué)學(xué)院，上海 200092）

本文僅討論無(wú)向的有限的簡(jiǎn)單圖，未提及的定義和定理參見(jiàn)文獻(xiàn)［1］。對(duì)于一個(gè)點(diǎn)v，用dG(v)、NG(v)（不造成歧義的情況下可以簡(jiǎn)寫(xiě)為d(v)、N(v)）來(lái)定義點(diǎn)v的度數(shù)和點(diǎn)v的鄰點(diǎn)集合。對(duì)于圖G，分別用V(G)、E(G)、Δ(G)、δ(G)和g(G)來(lái)定義它的點(diǎn)集、邊集、最大度、最小度和圍長(zhǎng)（圖G中最小圈的長(zhǎng)度）。將平面圖嵌入平面后，用F(G)表示其面集，一個(gè)k+-點(diǎn)（或k--點(diǎn)）v表示點(diǎn)v的度數(shù)至少為k（或至多為k）。類似的，用dG(f)表示面f的度數(shù)，一個(gè)k+-面（或k--面）f表示點(diǎn)f的度數(shù)至少為k（或至多為k）。

圖G的一個(gè)正常k-染色指的是從點(diǎn)集V(G)到顏色集{1，2，...，k}的映射c，使得圖G中任意相鄰的兩點(diǎn)均不同色。用c(v)定義點(diǎn)v的顏色，用Ci(v)定義在N(v)中出現(xiàn)過(guò)i次的顏色所構(gòu)成的集合。

圖G的最大平均度一般記作mad(G)，定義為

圖的frugal-染色首先由Hind等人在文獻(xiàn)［2］中提出。在圖G的一個(gè)點(diǎn)染色c中，如果每種顏色在點(diǎn)v的鄰點(diǎn)中至多出現(xiàn)k-1次，就稱點(diǎn)v是k-frugal的。如果圖G中每個(gè)點(diǎn)都是k-frugal的，就稱圖G是k-frugal可染的，這個(gè)染色稱作圖G的k-frugal 染色。圖G的kfrugal色數(shù)，記作χk(G)，指的是使圖G滿足k-frugal可染所需的最少的顏色數(shù)量。由定義易知，χk(G)≥

圖的frugal-染色可以推廣到列表染色上。設(shè)L為一個(gè)函數(shù)，它將圖G中的每個(gè)點(diǎn)v都映射到一個(gè)由一些正整數(shù)構(gòu)成的集合L(v)上，L(v)稱作點(diǎn)v的列表。如果一個(gè)染色c：V→N滿足c(v)∈L(v)對(duì)于所有v∈V都成立，就稱這個(gè)染色為圖G關(guān)于L的列表染色，或L-染色，并且稱圖G是L-可染的。如果圖G中每個(gè)點(diǎn)的列表長(zhǎng)度均滿足|L(v)|=l，就稱這個(gè)列表為圖G的l-列表。如果對(duì)于任意l-列表L，圖G都是k-frugalL-可染的，則滿足這個(gè)條件的最小正整數(shù)l就稱作圖G的k-frugal 列表色數(shù)，記作chk(G)。

圖G的lineark-染色是圖的一種特殊的正常k-染色。linear染色的定義是由Yuster［3］首先提出的，要求圖G中由任意兩種顏色導(dǎo)出的子圖，均為若干條內(nèi)部不相交的路。圖G的linear-色數(shù)，記作lc(G)，指的是使圖G滿足lineark-染色所需要的最小整數(shù)k。

顯然，一個(gè)linear染色必定為3-frugal染色，但是反過(guò)來(lái)并不一定成立，因?yàn)閘inear染色中不允許雙色圈的存在。更多關(guān)于linear染色的結(jié)果參見(jiàn)文獻(xiàn)［4-9］。

圖G的2-distancek-染色是圖的另一種特殊的正常k-染色。2-distance染色的定義是由Wegner［10］首先提出的，要求圖G中距離小于等于2的兩個(gè)點(diǎn)均不同色。圖G的2-distance-色數(shù)，指的是使圖G滿足2-distancek-染色所需要的最小整數(shù)k。

顯然，2-distance染色的定義2-frugal染色的定義相同。更多關(guān)于2-distance染色的結(jié)果參見(jiàn)文獻(xiàn)［11-24］。

關(guān)于一般的k-frugal染色，Amini等人在文獻(xiàn)［25］中證明了對(duì)于任意k≥1，平面圖G都滿足

1 主要結(jié)論

下面討論稀疏圖的k-frugal列表染色，并得出如下結(jié)論。

2 定理1.1的證明

下面首先證明圖G的一些結(jié)構(gòu)，然后通過(guò)Discharging的方法來(lái)證明這個(gè)結(jié)論。

引理2.1.δ(G)≥2。

證明：反證法，假設(shè)圖G含有一個(gè)1-點(diǎn)v。由圖G的定義知，G-v有一個(gè)k-frugalL-染色c。設(shè)NG(v)=u，此時(shí)若想把染色擴(kuò)充到圖G上，點(diǎn)v禁用的顏色為c(u)以及在NG(u)中出現(xiàn)過(guò)k-1 次的顏色（即Ck-1(u)）。因此禁用的顏色至多為

因此，可以將染色擴(kuò)充到圖G上，矛盾。

由圖G的定義知，G-v有一個(gè)k-frugalL-染色c。此時(shí)若想把染色擴(kuò)充到圖G上，點(diǎn)v禁用的顏色為諸c(vi)以及在NG(vi)中出現(xiàn)過(guò)k-1 次的顏色（即Ck-1(vi)）。因此禁用的顏色至多為

這樣就可以將染色擴(kuò)充到圖G上，矛盾。

為了方便證明，下面給出一些定義。

下面通過(guò)Discharging的方法得到一個(gè)矛盾。給每個(gè)點(diǎn)v賦初始權(quán)ω(v)=d(v)，因此有

對(duì)于每個(gè)x∈V，都通過(guò)特定的權(quán)轉(zhuǎn)移規(guī)則（權(quán)只能從一個(gè)元素轉(zhuǎn)移到另一個(gè)元素，故總和不變），得到一個(gè)新權(quán)ω*(x)，因?yàn)樵跈?quán)轉(zhuǎn)移的過(guò)程中總和不變，所以仍有

如果在權(quán)轉(zhuǎn)移后，得到ω*(x)＞mad(G)對(duì)于所有x∈V均成立，則有

這樣就得到一個(gè)矛盾，從而定理得證。

下面給出權(quán)轉(zhuǎn)移規(guī)則，Discharging 規(guī)則：

綜上，得到了一個(gè)矛盾，定理得證。

3 定理1.2的證明

下面首先證明圖G的一些結(jié)構(gòu)，然后通過(guò)discharging的方法來(lái)證明這個(gè)結(jié)論。

引理3.1.δ(G)≥2。

證明：證明方法與引理2.1相同。

引理3.2.G中不含與3--點(diǎn)相鄰的2-點(diǎn)。

證明：假設(shè)定理不成立，G中存在一個(gè)2-點(diǎn)v，且其與一個(gè)3--點(diǎn)u相鄰。由于圖G為極小反例，G-v有一個(gè)k-frugalL-染色c。設(shè)NG(v)={u，w}，則v禁用的顏色為c(u)，c(w)以及在NG(w)中出現(xiàn)過(guò)k-1次的顏色（i.e.Ck-1(w)），所以點(diǎn)v禁用的顏色至多為

因此，可以將染色c擴(kuò)充到圖G上，矛盾。

引理3.3.G中不含與3個(gè)2-點(diǎn)相鄰的4-點(diǎn)。

證明：假設(shè)定理不成立，G中含有一個(gè)4-點(diǎn)v，且其與3個(gè)2-點(diǎn)x，y，z相鄰。設(shè)x1，y1，z1分別為x，y，z的另一個(gè)鄰點(diǎn)，v1為v的第4個(gè)鄰點(diǎn)。由于G為極小反例，G-{v，x，y，z} 有 一 個(gè)k-frugalL-染 色c。設(shè) 點(diǎn)w∈{v，x，y，z}，則w禁用的顏色為c(w1)以及在NG(w1)出現(xiàn)過(guò)k-1次的顏色（i.e.Ck-1(w1)），因此點(diǎn)w禁用的顏色為

設(shè)L*(w)=L(w)({c(w1)}∪Ck-1(w1))，則|L*(w)|≥2，其中，w∈{v，x，y，z}。

首先用c(x)∈L*(x){c(v1)}中的顏色染x，用c(v)∈L*(v){c(x)} 中的顏色染v，用c(y)∈L*(y){c(v)} 中的顏色染y，用c(z)∈L*(z){c(v)}中的顏色染z。容易驗(yàn)證這是圖G的一個(gè)k-frugalL-染色，矛盾。

引理3.4.G中不含與5個(gè)2-點(diǎn)相鄰的5-點(diǎn)。

證明：假設(shè)定理不成立，G中含有一個(gè)5-點(diǎn)v，且NG(v)={x1，x2，…，x5}，dG(xi)=2，yi為xi的另一個(gè)鄰點(diǎn)（其中i=1，2，…，5）。由于G為極小反例，G{v，x1，x2，…，x5} 有一個(gè)k-frugalL-染色c。?1 ≤i≤5，點(diǎn)xi禁用的顏色為c(yi)和在NG(yi)中出現(xiàn)過(guò)k-1 次的顏色（i.e.Ck-1(yi)）。設(shè)L*(xi)=L(xi)({c(yi)}∪Ck-1(yi))，易得|L*(xi)|≥對(duì)于點(diǎn)v，易得

下面將染色c擴(kuò)充到圖G上。

首先用L*(x1)中的顏色染x1，這個(gè)顏色記作a；然后用L*(x2){a}中的顏色染x2，這個(gè)顏色記作c(x2)；用L*(v){a，c(x2) }中的顏色染v，這個(gè)顏色記作b；最后用L*(xi)中的顏色染xi，其中i=3，4，5。容易驗(yàn)證當(dāng)c(x3)=c(x4)=c(x5)=a和c(x3)=c(x4)=c(x5)=c(x2)均不成立的時(shí)候，這個(gè)染色為圖G的k-frugalL-染色。不失一般性，假定L*(xi)={a，b}且c(xi)=a對(duì)于i=3，4，5均成立。

如果L*(x1)≠{a，b}，那么可以用L*(x1){a}中的顏色給x1重新染色，容易驗(yàn)證這是圖G的k-frugalL-染色。

下面假設(shè)L*(x1)={a，b}。重新給x1和x5染上顏色b，用c(v)∈L(v){a，b}中的顏色重新染v，用L*(x2){c(v)}中的顏色重新染x2，容易驗(yàn)證這是圖G的一個(gè)k-frugalL-染色，矛盾。

接下來(lái)通過(guò)discharging的方法來(lái)獲得一個(gè)矛盾，首先給每個(gè)點(diǎn)v賦初始權(quán)ω(v)=d(v)，設(shè)權(quán)轉(zhuǎn)移后得到的新權(quán)圍ω*(v)。

下面給出權(quán)轉(zhuǎn)移規(guī)則，每個(gè)4+-點(diǎn)v轉(zhuǎn)移到相鄰的2-點(diǎn)。

下面來(lái)驗(yàn)證ω*(x)≥3對(duì)于所有x∈V均成立。

設(shè)v為一個(gè)k-點(diǎn)。

如果k=3，由引理3.2，3點(diǎn)之不與2-點(diǎn)相鄰，則ω(v)≥3。

如果k=2，由引理3.2，2-點(diǎn)只能與4+-點(diǎn)相鄰，則

綜上，得到了一個(gè)矛盾，定理得證。

4 定理1.3的證明

下面首先證明圖G的一些結(jié)構(gòu)，然后通過(guò)discharging的方法來(lái)證明這個(gè)結(jié)論。

引理4.1.δ(G)≥2。

證明：證明方法與引理2.1相同。

證明：證明方法與引理2.2相同。

引理4.3.若v為2-點(diǎn) 且NG(v)={u，w}，d(u)≤d(w)，則d(u)≥2(k-1)+1 ≥7。

證明：假設(shè)d(u)≤2(k-1)，帶入引理4.2，得d(w)＞Δ，矛盾。

引理4.4.若v為3-點(diǎn)，NG(v)={x，y，z}，且d(x)≤d(y)≤d(z)，則d(z)≥d(y)≥k≥4。

證明：假設(shè)d(y)≤k-1，帶入引理4.2，得d(z)＞Δ，矛盾。

引理4.5.不存在與6個(gè)2-點(diǎn)相鄰的7-點(diǎn)。

證明：設(shè)v為一個(gè)7-點(diǎn)，NG(v)={x1，x2，x3，x4，x5，x6，u}，其中d(xi)=2，NG(xi)={v，yi}（i=1，2，…，6）。

由圖G的極小性，圖G-{v，x1，x2，x3，x4，x5，x6}有一個(gè)k-frugalL-染色c。此時(shí)點(diǎn)v被禁用的顏色為c(u)以及在NG(u)中出現(xiàn)k-1次的顏色。因此點(diǎn)v被禁用的顏色至多為

設(shè)點(diǎn)v的可用顏色集為L(zhǎng)*(v)，則|L*(v)|≥3。

同理可得

點(diǎn)xi∈{x1，x2，x3，x4，x5，x6}的可用顏色集為|L*(xi)|≥3。

下面將這個(gè)染色c擴(kuò)充到圖G上。

給x1染顏色c1∈L*(x1){c(u)}，給x2染顏色c2∈L*(x2){c(u)，c1}，給v染顏色c3∈L*(v){c1，c2}。

給x3染顏色a1∈L*(x3){c3}，給x4染顏色b1∈L*(x4){c3，a1}。

給x5染顏色a2∈L*(x5){c3}，給x6染顏色b2∈L*(x6){c3，a2}。

因此，a1≠b1，a2≠b2，c1≠c(u)，c2≠c(u)。

集合c1，c2，a1，b1，a2，b2，c(u)中同種顏色至多出現(xiàn)3次，因此得到的染色為圖G的一個(gè)k-frugalL-染色，矛盾。

引理4.6.設(shè)k為正整數(shù)，8 ≤k≤9，則不存在與k個(gè)2-點(diǎn)相鄰的k-點(diǎn)。

證明：這里不妨假設(shè)k=9，因?yàn)橹灰猭=9成立，k=8的情況類似可證。

設(shè)點(diǎn)v為一個(gè)9-點(diǎn)，且與9 個(gè)2-點(diǎn)相鄰。NG(v)={x1，x2，…，x9}，yi為點(diǎn)xi異于點(diǎn)v的另一個(gè)鄰點(diǎn)。由G的極小性，圖G-{v，x1，x2，…，x9}有一個(gè)k-frugalL-染色c。

此時(shí)點(diǎn)xi被禁用的顏色為c(yi)以及在NG(yi)中出現(xiàn)k-1次的顏色，點(diǎn)v可以染其本身列表中的任意一種顏色。

設(shè)點(diǎn)v的可用顏色集為L(zhǎng)*(v)，點(diǎn)xi的可用顏色集為L(zhǎng)*(xi)（其 中i=1，2，…，9），則|L*(v)|=|L(v)|≥1+3=4，|L*(xi)|≥3。

下面采用如下方式將這個(gè)染色c擴(kuò)充到原圖G上。

給x1染c(x1)∈L*(x1)，

給x2染c(x2)∈L*(x2){c(x1)}，

給x3染c(x3)∈L*(x3){c(x1)，c(x2)}，

給x4染c(x4)∈L*(x4)，

給x5染c(x5)∈L*(x5){c(x4)}，

給x6染c(x6)∈L*(x6){c(x4)，c(x5)}，

給x7染c(x7)∈L*(x7)，

給x8染c(x8)∈L*(x8){c(x7)}，

給x9染c(x9)∈L*(x9){c(x7)，c(x8)}，

此時(shí)，點(diǎn)x1，x2，x3的顏色互不相同，點(diǎn)x4，x5，x6的顏色互不相同，點(diǎn)x7，x8，x9的顏色互不相同。

設(shè)S=，則3 ≤|S|≤9。

如果L(v)S≠?，給點(diǎn)v染c(v)∈L(v)S，就可以把這個(gè)染色c擴(kuò)充到圖G上，矛盾。

下面設(shè)L(v)?S，對(duì)k進(jìn)行分類討論。

情況1.當(dāng)k=4 時(shí)，|L*(v)|=|L(v)|=

此時(shí)L(v)中必然存在3種顏色，這3種顏色在S中出現(xiàn)的次數(shù)均小于等于1。因?yàn)槿绻挥袃煞N顏色在S中出現(xiàn)不超過(guò)一次的話，可以推出S≥4×2+2×1=10，矛盾。

而且，此時(shí)必然有Ck-1(v)=C3(v)≤1，因?yàn)槿绻鹼Ck-1(v)|≥2，可以推出S≥2×3+4×1=10，矛盾。

此時(shí)不妨設(shè)c(xi)∈L(v)∩C1(v)，首先擦掉xi的顏色，然后給點(diǎn)v染c(xi)，最后用集合L*(xi)[{c(xi) }∪C3(v) ]中的染色給點(diǎn)xi染色，即可將染色擴(kuò)充到圖G上。

情況2.當(dāng)k≥5 時(shí)，|L*(v)|=|L(v)|=

根據(jù)前邊的染色方法，得知?c∈L(v)，顏色c在集合S中出現(xiàn)的次數(shù)不超過(guò)3，即C4(v)=?。

此時(shí)集合L(v)中至多有兩種顏色在S中出現(xiàn)的次數(shù)等于3（不妨設(shè)這兩種顏色為{1，2}），因?yàn)槿绻?種顏色在S中出現(xiàn)的次數(shù)等于3，則可以推出|S|≥3×3+1×1=10，矛盾。

因此，L(v)中總有一種顏色，其在S中出現(xiàn)的次數(shù)小于等于2，不妨設(shè)這個(gè)顏色為{3}。

集合S中至多有兩個(gè)點(diǎn)顏色為3，不妨設(shè)為{vi，vj}，首先擦掉這兩個(gè)點(diǎn)的顏色，給點(diǎn)v染顏色3，然后給點(diǎn)vi染集合L*(vi){1，3}中的顏色，給點(diǎn)vj染集合L*(vj){2，3}中的顏色，容易驗(yàn)證此時(shí)染色滿足5-frugal 的條件，因此可以將這個(gè)染色擴(kuò)充到圖G上。矛盾。

為了方便下列引理的證明，給出幾個(gè)定義。若一個(gè)3-點(diǎn)與3個(gè)4+-點(diǎn)相鄰，就稱其為重3-點(diǎn)，反之稱為輕3-點(diǎn)。若一個(gè)8-點(diǎn)與7個(gè)2-點(diǎn)和一個(gè)重3-點(diǎn)相鄰，就稱其為輕8-點(diǎn)。

引理4.7.不存在與7個(gè)2-點(diǎn)和一個(gè)輕3-點(diǎn)相鄰的8-點(diǎn)。

下面將染色c擴(kuò)充到原圖G上。

給x8染c(x8)∈L*(x8)，

給x1染c(x1)∈L*(x1){c(x8)}，

給x2染c(x2)∈L*(x2){c(x8)，c(x1)}，

給x3染c(x3)∈L*(x3)，

給x4染c(x4)∈L*(x4){c(x3)}，

給x5染c(x5)∈L*(x5){c(x3)，c(x4)}，

給x6染c(x6)∈L*(x6)，

給x7染c(x7)∈L*(x7){c(x6)}，

此時(shí)，點(diǎn)x8，x1，x2的顏色互不相同，點(diǎn)x3，x4，x5的顏色互不相同，點(diǎn)x6，x7的顏色互不相同。

設(shè)S=，則3 ≤|S|≤8。

如果L(v)S≠?，令c(v)∈L(v)S，就可以把這個(gè)染色擴(kuò)充到圖G上，矛盾。

下面不妨設(shè)L(v)?S，對(duì)k進(jìn)行分類討論

情況1.當(dāng)k=4 時(shí)，|L*(v)|=|L(v)|=≥3+3=6從而|S|≥L(v)≥6。

此時(shí)L(v)中必然存在3種顏色，這3種顏色在S中出現(xiàn)的次數(shù)均小于等于1。因?yàn)槿绻挥袃煞N顏色在S中出現(xiàn)不超過(guò)一次的話，可以推出S≥4×2+2×1=10，矛盾。

而且，此時(shí)必然有Ck-1(v)=C3(v)≤1，因?yàn)槿绻鹼Ck-1(v)|≥2，可以推出S≥2×3+4×1=10，矛盾。

此時(shí)不妨設(shè)c(xi)∈L(v)∩C1(v)，首先擦掉xi的顏色，然后給點(diǎn)v染c(xi)，最后用集合L*(xi)[{c(xi) }∪C3(v) ]中的染色給點(diǎn)xi染色，即可將染色擴(kuò)充到圖G上。

情況2.當(dāng)k≥5 時(shí)，|L*(v)|=|L(v)|=≥4，從而|S|≥L(v)≥4。

根據(jù)前邊的染色方法，得知?c∈L(v)，顏色c在集合S中出現(xiàn)的次數(shù)不超過(guò)3，即C4(v)=?。

此時(shí)集合L(v)中至多有兩種顏色在S中出現(xiàn)的次數(shù)等于3（不妨設(shè)這兩種顏色為{1，2}），因?yàn)槿绻?種顏色在S中出現(xiàn)的次數(shù)等于3，則可以推出|S|≥3×3+1×1=10，矛盾。

由于L(v){1，2，c(x8)}≠?，從該集合中任取一個(gè)顏色c1，則集合S中至多有兩個(gè)點(diǎn)的顏色為c1，不妨設(shè)存在兩個(gè)點(diǎn)的顏色為c1（若只有一個(gè)點(diǎn)顏色為c1，證明方法類似），且這兩個(gè)點(diǎn)均不為x8。設(shè)這兩個(gè)點(diǎn)為{vi，vj}。首先擦掉這兩個(gè)點(diǎn)的顏色，給點(diǎn)v染顏色c1，然后給點(diǎn)vi染集合L*(vi){c1，1}中的顏色，給點(diǎn)vj染集合L*(vj){c1，2}中的顏色，容易驗(yàn)證此時(shí)染色滿足5-frugal的條件，因此可以將這個(gè)染色擴(kuò)充到圖G上。矛盾。

引理4.8.不存在與兩個(gè)輕8-點(diǎn)相鄰的3-點(diǎn)。

證明：由定義，得知與輕8-點(diǎn)相鄰的3-點(diǎn)一定是重3-點(diǎn)。

上述3種染色方案中點(diǎn)v使用的列表均不完全相同，因此cx(v)，cy(v)，cz(v)這3種顏色不可能完全相同，所以總可以找到兩個(gè)方案，不妨設(shè)為cx，cy，滿足cx(v)≠cy(v)，這里不妨設(shè)cx(v)=a，cy(v)=b。

容易驗(yàn)證此時(shí)得到的染色為原圖的一個(gè)k-frugalL-染色，因此可以將染色c擴(kuò)充到圖G上，矛盾。

這樣就通過(guò)discharging的方法來(lái)獲得一個(gè)矛盾，首先給每個(gè)點(diǎn)v賦初始權(quán)ω(v)=d(v)，設(shè)權(quán)轉(zhuǎn)移后得到的新權(quán)為ω*(v)。

下面給出權(quán)轉(zhuǎn)移規(guī)則：

如果k=8，由引理4.6，點(diǎn)v周?chē)炼啻嬖?個(gè)2-點(diǎn)，下面分兩種情況討論。

這樣就得到一個(gè)矛盾，定理得證。

作者貢獻(xiàn)聲明：

房啟明：提出研究問(wèn)題，設(shè)計(jì)研究方案，起草論文；

張莉：對(duì)發(fā)表文章作最后的審閱和定稿，并在研究的過(guò)程中提出諸多啟發(fā)性觀點(diǎn)。