房啟明，張 莉

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

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

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

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

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

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

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

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

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

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

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

1 主要結(jié)論

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

2 定理1.1的證明

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

引理2.1.δ(G)≥2。

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

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

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

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

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

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

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

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

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

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

綜上，得到了一個矛盾，定理得證。

3 定理1.2的證明

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

引理3.1.δ(G)≥2。

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

引理3.2.G中不含與3--點相鄰的2-點。

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

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

引理3.3.G中不含與3個2-點相鄰的4-點。

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

引理3.4.G中不含與5個2-點相鄰的5-點。

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

下面將染色c擴充到圖G上。

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

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

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

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

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

下面來驗證ω*(x)≥3對于所有x∈V均成立。

設(shè)v為一個k-點。

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

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

綜上，得到了一個矛盾，定理得證。

4 定理1.3的證明

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

引理4.1.δ(G)≥2。

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

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

引理4.3.若v為2-點 且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-點，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個2-點相鄰的7-點。

證明：設(shè)v為一個7-點，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}有一個k-frugalL-染色c。此時點v被禁用的顏色為c(u)以及在NG(u)中出現(xiàn)k-1次的顏色。因此點v被禁用的顏色至多為

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

同理可得

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

下面將這個染色c擴充到圖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的一個k-frugalL-染色，矛盾。

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

證明：這里不妨假設(shè)k=9，因為只要k=9成立，k=8的情況類似可證。

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

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

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

下面采用如下方式將這個染色c擴充到原圖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)}，

此時，點x1，x2，x3的顏色互不相同，點x4，x5，x6的顏色互不相同，點x7，x8，x9的顏色互不相同。

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

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

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

情況1.當k=4 時，|L*(v)|=|L(v)|=

此時L(v)中必然存在3種顏色，這3種顏色在S中出現(xiàn)的次數(shù)均小于等于1。因為如果只有兩種顏色在S中出現(xiàn)不超過一次的話，可以推出S≥4×2+2×1=10，矛盾。

而且，此時必然有Ck-1(v)=C3(v)≤1，因為如果|Ck-1(v)|≥2，可以推出S≥2×3+4×1=10，矛盾。

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

情況2.當k≥5 時，|L*(v)|=|L(v)|=

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

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

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

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

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

引理4.7.不存在與7個2-點和一個輕3-點相鄰的8-點。

下面將染色c擴充到原圖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)}，

此時，點x8，x1，x2的顏色互不相同，點x3，x4，x5的顏色互不相同，點x6，x7的顏色互不相同。

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

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

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

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

此時L(v)中必然存在3種顏色，這3種顏色在S中出現(xiàn)的次數(shù)均小于等于1。因為如果只有兩種顏色在S中出現(xiàn)不超過一次的話，可以推出S≥4×2+2×1=10，矛盾。

而且，此時必然有Ck-1(v)=C3(v)≤1，因為如果|Ck-1(v)|≥2，可以推出S≥2×3+4×1=10，矛盾。

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

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

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

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

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

引理4.8.不存在與兩個輕8-點相鄰的3-點。

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

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

容易驗證此時得到的染色為原圖的一個k-frugalL-染色，因此可以將染色c擴充到圖G上，矛盾。

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

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

如果k=8，由引理4.6，點v周圍至多存在7個2-點，下面分兩種情況討論。

這樣就得到一個矛盾，定理得證。

作者貢獻聲明：

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

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