最大次數(shù)為3的色指數(shù)臨界圖的一種構(gòu)造

徐繼軍， 時(shí)文俊

(1．鄭州師范學(xué)院數(shù)學(xué)與統(tǒng)計(jì)學(xué)院 河南 鄭州450044;

2．鄭州大學(xué)升達(dá)經(jīng)貿(mào)管理學(xué)院共同學(xué)科部 河南鄭州451191)

0 引言

本文考慮的圖都是簡單圖，未定義的術(shù)語和符號可參看文［1－2］．

給定一個(gè)圖G，用E(G)和V(G)表示G的邊集和點(diǎn)集．G的頂點(diǎn)v的次數(shù)是指G中與v相關(guān)聯(lián)的邊的數(shù)目，用Δ(G)表示G的最大次數(shù)．與點(diǎn)v相鄰點(diǎn)的集合記為NG(v)或N(v)．

圖G的k-(邊)著色是一個(gè)映射π:E(G)→{1，2，…，k}，使得G的相鄰邊沒有相同的象［4］．圖G的色指數(shù)χ'(G)=min{kG有一個(gè)k-著色}．1965年，Vizing在［2］中證明了定理:對于任何簡單圖G，有χ'(G)=Δ(G)或χ'(G)=Δ(G)+1．如果χ'(G)=Δ(G)，稱G是1-類的，否則稱G是2-類的．如果G是連通的，2-類的，并且對G的每一條邊e，都有χ'(G－e)＜χ'(G)，稱G是(色指數(shù))臨界的．如果臨界圖G的最大次數(shù)是Δ，稱G是Δ-臨界的．

設(shè) v∈V(G)，若 π 是G的一個(gè)具有顏色集{1，2，…，k}的k-著色，令Cπ(v)={π(e)e∈E(G)，e是與v相關(guān)聯(lián)的邊}，C'π(v)={1，2，…，k}Cπ(v)．如果 i∈Cπ(v)，則稱顏色 i擊中 v;如果 i∈C'π(v)，則稱 i未擊中v或i未在v上表現(xiàn)．顯然G的一個(gè)k-著色π把E(G)劃分成k個(gè)不交的顏色類，記為E1，E2，…，Ek，其中對于邊e∈Ei有π(e)=i．因此，當(dāng)i≠ j時(shí)，Ei∪Ej的每個(gè)連通分支是一條鏈(開或閉)．如果i∈C'π(v)，j∈{1，2，…，k}，則 Ei∪Ej中包含 v的連通分支是一條起始于 v的(i，j)π-鏈．當(dāng) j∈C'π(v)時(shí)，起始于v的(i，j)π-鏈?zhǔn)且粭l空鏈(不包含邊)．對于起始于v的(i，j)π-鏈的另一個(gè)端點(diǎn)u(≠v)，如果i和j一個(gè)擊中u，一個(gè)未擊中u，我們說這條鏈終止于u［3］．

1 主要結(jié)果

圖的四邊形擴(kuò)張的定義在文獻(xiàn)［4］中給出過，這里我們根據(jù)情況的不同又作了補(bǔ)充．

定義1 設(shè)G是最大次數(shù)為3的2-連通圖，xy，uv∈E(G)．在邊xy上添加兩個(gè)新點(diǎn)a，b，在邊uv上添加兩個(gè)新點(diǎn)c，d，再添加兩條新邊ad和bc，這樣得到的圖記作G{xy，uv}，abcda是它的一個(gè)四邊形．根據(jù)邊xy和uv是否獨(dú)立及新點(diǎn)的鄰接關(guān)系的不同，定義5種類型的四邊形擴(kuò)張:

1)若xy和uv是獨(dú)立的，且x，v分別與a，d相鄰，則稱G{xy，uv}是G的Ⅰ-型四邊形擴(kuò)張;

2)若xy和uv是獨(dú)立的，且x，v分別與a，c相鄰，則稱G{xy，uv}是G的Ⅱ-型四邊形擴(kuò)張;

3)若xy與uv僅有一個(gè)點(diǎn)重合，設(shè)y與u重合，且x，v分別與a，d相鄰，則稱G{xy，yv}是G的Ⅲ-型四邊形擴(kuò)張;

4)若xy與uv僅有一個(gè)點(diǎn)重合，設(shè)y與u重合，若x，v分別與a，c相鄰，則稱G{xy，yv}是G的Ⅳ-型四邊形擴(kuò)張;

5)在邊xy上依次添加4個(gè)新點(diǎn)a，b，d，c，使得a與x相鄰，c與y相鄰，再添加兩條新邊ad和bc，所得到的圖記作G{xy，xy}，abcda是它的一個(gè)四邊形，稱G{xy，xy}為G的Ⅴ-型四邊形擴(kuò)張．

G{xy，uv}也稱G的1-四邊形擴(kuò)張．若 x1y1，u1v1∈E(G{xy，uv})，則稱 G{xy，uv}的1-四邊形擴(kuò)張G{xy，uv}{x1y1，u1v1}是G的2-四邊形擴(kuò)張．一般地，如果Q是G的一個(gè)(k－1)-四邊形擴(kuò)張的1-四邊形擴(kuò)張，則稱Q是G的k-四邊形擴(kuò)張．由于添加的4個(gè)點(diǎn)的次數(shù)都為3，故四邊形擴(kuò)張保持2次點(diǎn)的個(gè)數(shù)不變，且4k．令 Qk(G)={Q Q是G的k-四邊形擴(kuò)張}．

定理1 設(shè)H=G{xy，uv}，如果G是1-類的，則H也是1-類的．

證明 設(shè)H是G的Ⅰ-型四邊形擴(kuò)張．由于G是1-類的，令π是G的一個(gè)具有顏色集{i，j，k}的3-著色，不妨設(shè) π(xy)=i．如果π(uv)=i，令σ(xa)=σ(by)=σ(cu)=σ(dv)=i，σ(ad)=σ(bc)=j，σ(ab)=σ(cd)=k，對于H的其他邊e，σ(e)=π(e)，則 σ即為H的一個(gè)3-著色．如果 π(uv)=j，令 σ(xa)=σ(by)=σ(cd)=i，σ(ab)=σ(cu)=σ(dv)=j，σ(ad)=σ(bc)=k，對于H的其他邊e，σ(e)=π(e)，則σ即為H的一個(gè)3-著色．如果π(uv)=k，類似可得H的一個(gè)3-著色，因此H是1-類的．

注對于其他4種類型的四邊形擴(kuò)張也有同樣的結(jié)果．

引理1［5－6］設(shè) G 是一 Δ-臨界圖，xy∈E(G)，π 是 G －xy的一個(gè) Δ-著色，則對任意的 i∈ C'π(x)，j∈C'π(y)，起始于 x 的(i，j)π-鏈必終止于 y．

定理2 設(shè)G是3-臨界的，xy和uv是G的兩條獨(dú)立邊，π是G－xy的具有顏色集{i，j，k}的一個(gè)3-著色．設(shè) i∈C'π(x)，j∈C'π(y)，若邊 uv不在起始于 x 的(i，j)π-鏈上，而在另外一條(i，j)π-開鏈上，則G{xy，uv}是 1-類的．

證明 若G{xy，uv}是G的Ⅰ-型四邊形擴(kuò)張，則xa，by，uc，vd∈E(G{xy，uv})．由于uv不在起始于x的(i，j)π-鏈上，而在另外一條(i，j)π-開鏈上，不妨設(shè) π(uv)=i．在 G －{xy，uv}中，交換起始于 u的(i，j)π-鏈的顏色，得到 G － {xy，uv}的一個(gè) 3-著色 σ 使得 i∈C'σ(v)，j∈C'σ(u)．令 σ(xa)= σ(bc)=σ(vd)=i，σ(yb)=σ(ad)=σ(uc)=j，σ(ab)=σ(cd)=k，這樣σ擴(kuò)充為G{xy，uv}的一個(gè)3-著色，因此G{xy，uv}是1-類的．類似可證，若G{xy，uv}是G的Ⅱ-型四邊形擴(kuò)張，G{xy，uv}也是1-類的．

定理3 設(shè)G是3-臨界的，xy和uv是G的兩條獨(dú)立邊，且x，y，u，v中有一個(gè)二次點(diǎn)．若G{xy，uv}是2-類的，則 G{xy，uv}=H 是3-臨界的．

證明 設(shè)W={xa，yb，ab，ad，cd，bc，dv，cu}，則(G－{xy，uv})∪W是G的Ⅰ-型四邊形擴(kuò)張，不妨設(shè)d(x)=2，π是G－xy的具有顏色集{1，2，3}一個(gè)3-著色，則=1 且 C'π(x)∩C'π(y)=?．不妨設(shè) C'π(x)={1，2}，C'π(y)={3}．由于 G 是臨界的，且 G{xy，uv}是 2-類的，只需證明 W中的每條邊都是臨界的即可．

情形1 π(uv)=3．

令σ(ad)=σ(bc)=1，σ(ab)=σ(cd)=2，σ(dv)=σ(cu)=σ(yb)=3，對 H 的其他邊 e，σ(e)=π(e)，則σ是H－xa的一個(gè)3-著色，即xa是H的臨界邊．同理可證yb，ad，dv，ab是H的臨界邊．

下證bc，cd，cu是H的臨界邊．因?yàn)镠是2-類的，由定理2，邊uv在起始于x的(1，3)π-鏈上，或者經(jīng)過邊 uv的(1，3)π-鏈?zhǔn)且粋€(gè)圈．

情形1．1 若邊uv在起始于x的(1，3)π-鏈上．

如果起始于x的(1，3)π-鏈先經(jīng)過v，在G －{xy，uv}中交換起始于u 的(3，1)π-鏈的顏色，得到G －{xy，uv}的一個(gè)3-著色 σ，使得1∈Cσ'(u)，1∈Cσ'(y)．令 σ(yb)=σ(ad)=σ(cu)=1，σ(xa)=σ(cd)=2，σ(ab)=σ(dv)=3，則σ是H－bc的一個(gè)3-著色，即bc是H的臨界邊．同理可證cd，cu是H的臨界邊．

情形1．2 若經(jīng)過邊uv的(1，3)π-鏈?zhǔn)且粋€(gè)圈．

交換起始于 x 的(1，3)π-鏈的顏色，可得到一著色 σ，使得 C'σ(x)={3，2}，C'σ(y)={1}．令 σ(yb)=σ(ad)=1，σ(ab)=σ(cd)=2，σ(xa)=σ(dv)=σ(cu)=3，則σ是H－bc的一個(gè)3-著色，即bc是H的臨界邊．同理可證cd，cu是H的臨界邊．

情形2 π(uv)=1或2．不妨設(shè)π(uv)=1．

令σ(ab)=σ(dv)=σ(cu)=1，σ(ad)=σ(bc)=2，σ(cd)=σ(yb)=3，對 H 的其他邊 e，σ(e)=π(e)，則σ是H－xa的一個(gè)3-著色，即xa是H的臨界邊．同理可證yb，bc，ab，cd，cu，ad是H的臨界邊．

下證dv是H的臨界邊．由定理2，邊uv在起始于x的(1，3)π-鏈上，或者經(jīng)過uv的(1，3)π-鏈?zhǔn)且粋€(gè)圈．

情形2．1 若邊uv在起始于x的(1，3)π-鏈上．

若起始于x的(1，3)π-鏈先經(jīng)過u，在G－{xy，uv}中交換起始于x終止于u的(1，3)π-鏈的顏色，得到G －{xy，uv}的一個(gè) 3-著色 σ，使得 3∈C'σ(x)，3∈C'σ(u)．令 σ(ab)= σ(cd)=1，σ(ad)= σ(bc)=2，σ(xa)=σ(yb)=σ(cu)=3，則σ是H－dv的一個(gè)3-著色，即dv是H的臨界邊．

若起始于x的(1，3)π-鏈先經(jīng)過v，在G－{xy，uv}中交換起始于x終止于v的(1，3)π-鏈的顏色，得到G －{xy，uv}的一個(gè)3-著色 σ，使得 3∈C'σ(x)，3∈C'σ(v)．令 σ(ab)= σ(cd)=1，σ(ad)= σ(bc)=2，σ(xa)=σ(yb)=σ(cd)=3，則σ是H－dv的一個(gè)3-著色，即dv是H的臨界邊．

情形2．2 若經(jīng)過邊uv的(1，3)π-鏈?zhǔn)且粋€(gè)圈．

交換起始于 x 終止于 y 的(1，3)π-鏈的顏色，可得到 G 的一個(gè) 3-著色 σ，使得 C'σ(x)={3，2}，C'σ(y)={1}，令σ(yb)=σ(ad)=σ(cu)=1，σ(ab)=σ(cd)=2，σ(xa)=σ(bc)=3，則 σ 是 H －dv的一個(gè)3-著色，即dv是H的臨界邊．

所有情形被考慮，故W中的每條邊都是H的臨界邊．綜上，G{xy，uv}=H是3-臨界的．

用類似的方法可證，對Ⅱ-型四邊形擴(kuò)張也有相同的結(jié)論．

引理2［4，7］設(shè)G是一最大次數(shù)為3的圖，H是對G的某個(gè)點(diǎn)作三角形擴(kuò)張得到的圖，則有(a)G是1-類的當(dāng)且僅當(dāng)H是1-類的;(b)G是3-臨界的當(dāng)且僅當(dāng)H是3-臨界的．

定理4 設(shè)G是最大次數(shù)為3的圖，xy和yv是G的兩條邊，H=G{xy，yv}是G的Ⅲ-型四邊形擴(kuò)張或Ⅳ-型四邊形擴(kuò)張，則(ⅰ)H是1-類的當(dāng)且僅當(dāng)G是1-類的;(ⅱ)H是3-臨界的當(dāng)且僅當(dāng)G是3-臨界的．

證明 若H是G的Ⅲ-型四邊形擴(kuò)張，則相當(dāng)于對圖G中的頂點(diǎn)y進(jìn)行兩次三角形擴(kuò)張，由引理2，結(jié)論成立．

現(xiàn)在設(shè)H 是 G 的Ⅳ-型四邊形擴(kuò)張，則 E(H)=E(G －{xy，yv})∪{xa，yb，ab，ad，cd，bc，cv，dy}．

(ⅰ)的充分性由定理1的注易得．證明必要性．設(shè)H是1-類的，σ是H的一個(gè)具有顏色集{1，2，3}的3-著色，先證 σ(xa)≠σ(cv)．事實(shí)上，若 σ(xa)=σ(cv)，不妨設(shè) σ(xa)=σ(cv)=1，則{σ(ab)，σ(ad)}={2，3}，{σ(cd)，σ(bc)}={2，3}．這樣，邊 by和 dy只能著顏色1，矛盾．

若d(y)=2，令π(xy)=σ(xa)，π(yv)=σ(cv)，對G的其他邊e，π(e)=σ(e)，則π是G的一個(gè)3-著色，因此G是1-類的．

若 d(y)=3，設(shè)NG(y)={x，v，p}，我們證明=3．因?yàn)?σ(xa)≠σ(cv)，所以只需證明 σ(yp)?{σ(xa)，σ(cv)}．否則，設(shè) σ(xa)=σ(yp)=1，則{σ(ab)，σ (ad)}={2，3}，{σ(by)，σ(dy)}={2，3}，這樣邊bc和cd只能著顏色1，矛盾．類似可證σ(yp)≠σ(cv)．令π(xy)=σ(xa)，π (yv)=σ(cv)，π(yp)=σ(yp)，對G的其他邊e，π(e)=σ(e)，則π是G的一個(gè)3-著色，因此G是1-類的．故(ⅰ)成立．

現(xiàn)在證(ⅱ)．若H是3-臨界的，由(ⅰ)知G是2-類的，且G中除了邊xy，yv外，其余的邊都是臨界邊．下證xy，yv是G的臨界邊．設(shè)σ是H－xa的一個(gè)具有顏色集{1，2，3}的3-著色，則σ(by)= σ(cv)或σ(dy)=σ(cv)．令π(yv)=σ(cv)，對G的其他邊e，π(e)=σ(e)，則π即為G－xy的一個(gè)3-著色，故xy是G的臨界邊．同理可證yv是G的臨界邊．

反之，設(shè)G是3-臨界的，由(ⅰ)知，H是2-類的且H中除了W中的邊以外，其余的邊都是臨界邊．只需證明W中的每條邊都是臨界邊．設(shè)π是G－xy的一個(gè)具有顏色集{1，2，3}的3-著色，則 C'π(x)=，且 C'π(x)∩C'π(y)= ?．不妨設(shè) C'π(x)={1}，C'π(y)={2}，π (yv)=1．

令σ(ab)=σ(dy)=σ(cv)=1，σ(by)=σ(cd)=2，σ(ad)=σ(bc)=3，對于H的其他邊e，σ(e)=π(e)，則σ為H－xa的一個(gè)3-著色，即xa是H的臨界邊．

同理可證ab，by，ad，bc，dy，cd，cv是H的臨界邊．故W中的邊都是H的臨界邊，因此H是3-臨界的．

定理5 對于Ⅴ-型四邊形擴(kuò)張，設(shè)H=G{xy，xy}，則

(A)H是1-類的當(dāng)且僅當(dāng)G是1-類的;(B)H是3-臨界的當(dāng)且僅當(dāng)G是3-臨界的．

證明 (A)的充分性由定理1的注易得．設(shè)H是1-類的，σ是H的一個(gè)具有顏色集{1，2，3}的3-著色，則 σ (xa)=σ (cy)．否則假設(shè) σ (xa)=1，σ (cy)=2，則{σ (ab)，σ (ad)}={1，3}，{σ (cd)，σ(bc)}={2，3}，這樣邊bd不能用這3種顏色著色，與H是1-類的矛盾．令π(xy)=σ(xa)，對G的其他邊e，π(e)=σ(e)，則π為G的一個(gè)3-著色，因此G是1-類的．故(A)成立．

現(xiàn)在證(B)．設(shè)W={xa，ab，bc，cd，ad，bd，cy}．若H是3-臨界的，由(A)知G是2-類的，且G中除了邊xy外，其余的邊都是臨界邊．下證xy是G的臨界邊．

設(shè)σ是H－xa的一個(gè)具有顏色集{1，2，3}的3-著色，對G－xy的任一邊e，令π(e)=σ(e)，則π是G－xy的一個(gè)3-著色，故xy是G的臨界邊．

反之，設(shè)G是3-臨界的，由(A)知，H是2-類的且H中除了W中的邊以外，其余的邊都是臨界邊．只需證明W中的邊都是臨界邊．設(shè)π是G－xy的一個(gè)具有顏色集{1，2，3}的3-著色，則C'π(x)∩C'π(y)= ?．不妨設(shè) C'π(x)={1}，C'π(y)={2}．令 σ (ad)= σ (bc)=1，σ (ab)= σ (cd)=2，σ(bd)=σ(cy)=3，對于H的其他邊e，σ(e)=π(e)，則σ為H－xa的一個(gè)3-著色，即xa是H的臨界邊．，

同理可證ad，ab，bd，cd，bc，cy是H的臨界邊．故W中的邊都是H的臨界邊，因此H是3-臨界的．

由以上定理的證明可以得到，一簡單圖G經(jīng)過一次四邊形擴(kuò)張變換之后，保持圖的臨界性不變．因此，若已知G是臨界圖，通過四邊形擴(kuò)張變換可以構(gòu)造出新的最大次數(shù)仍為3的階數(shù)更高的臨界圖．

［1］ Bondy J A ，Murty U S R．Graph Theory with Application［M］．London and Basingstoke:Macmillan Press，1976:1－103．

［2］ Vizing V G．Critical graphs with a given chromatic class［J］．Diskret Analiz，1965(5):9 －17．

［3］ 謝果．判定K-點(diǎn)連通圖與K-邊連通圖極小性定理［J］．四川師范大學(xué)學(xué)報(bào):自然科學(xué)版，2009，23(5):489－490．

［4］ 時(shí)文俊，張利民．圖的幾個(gè)變換［J］．河南師范大學(xué)學(xué)報(bào):自然科學(xué)版，2004，32(4):26－29．

［5］ Yap H P．Some Topics in Graph Theory［M］．London:Cambridge University Press，1986:1 －49．

［6］ 劉廣軍，劉信生．Pm∨Wn的點(diǎn)可區(qū)別全色數(shù)［J］．鄭州大學(xué)學(xué)報(bào):理學(xué)版，2009，41(1):6－8．

［7］ 董海燕，孫磊，孫艷麗．關(guān)于鄰點(diǎn)可區(qū)別全染色的幾個(gè)新結(jié)果［J］:廣西師范大學(xué)學(xué)報(bào):自然科學(xué)版，2005，23(3):41－43．