極小3-連通雙臨界圖的點著色數

林峰根

(福州大學數學與計算機科學學院，福建福州 350116)

0 引言

本文所考慮的圖都是有限的、無環的，但允許有重邊.我們說一個圖G=(V，E)是連通的，如果它的任意兩點都有一條路相連.假設X是V(G)的一個子集，即X?V(G)，從G中刪除X中的點以及與其中的點相關聯邊而得到的G的子圖，用G-X表示.如果＞k(k∈ N)，且對于每一個子集X?V(G)，＜k，G-X是連通的，則稱G為k-連通圖.一個圖G稱為雙臨界圖，如果G至少含有一條邊，且對于任意兩個不相同的點x，y，G-x-y具有完美匹配.一個圖G如果是3-連通雙臨界圖，那么G就稱為Brick.在文獻［1-2］中，Lovasz緊割分解定理表明，每一個匹配覆蓋圖G經過緊割分解，可得到一系列子圖Brick和Brace，而且，在不考慮重邊的意義下，緊割分解所得到的這一系列子圖是唯一的，即與分解過程中的緊割的選擇的先后順序無關.

因為很多問題都可歸結為Brick的相關問題，例如，計算圖的完美匹配格的維數，計算圖的完美匹配線性閉包集，以及判定一個圖是否有Pfaffian定向等等［3］，所以對Brick的結構性質的研究具有積極的意義.

設G是一個Brick.我們稱G是極小Brick，如果對于G的每一條邊e∈E(G)，G-e就不再是Brick.在文獻［4］中，Norine和Thomas證明了每一個頂點數n≥10的極小Brick至多只有5n/2-7條邊，而且每一個極小Brick至少有三個三度點.在文獻［5］中，Lin等人證明了每一個極小Brick至少有四個三度點.Carvalho等人對Brick還有更深入的研究，詳見文獻［6-9］.

目前，關于Brick的著色數的研究還沒有很好的結果.本文證明了每一個極小Brick的點著色數小于等于4.

1 Brick擴張

完全圖K4、C6以及Petersen圖稱為三個基本Brick(見圖1).

圖1 三個基本BrickFig.1 Three basic Bricks

設x是圖H的一個頂點.我們稱H':=H{x→(b1，b2，…，bk)}是由H經過分裂點x為b1，b2，…，bk而得到的圖，如果

(i)V(H')=V(H-x)∪ {b1，b2，…，bk};

(ii)E(H'):=E(H)，換句話說，就是E(H')與E(H)間存在1-1映射;

(iii)H'-{b1，b2，…，bk}=H-x;

(iv)v∈V(H-x)，vx∈E(H)，那么，對于某一個bi，bi∈V(H')，vbi∈E(H')，i∈{1，2，…，k}.

相似地，假設x和x'是圖H的兩個點，那么H″:=H{x→(b1，b2)，x'→(b'1，b'2)}是由H先經過分裂點x為b1，b2，再分裂點x'為b1'，b2'，而得到的圖.

為了證明本文的主要結果，還需復述一下Carvalho等［6］定義的Brick擴張的四種運算.借助于這四種運算，Carvalho等證明了每一個異于三個基本Brick的Brick都可由這三個基本Brick中的一個經過一系列擴張而得.假設H是一個Brick，見圖2.

A-擴張(加邊擴張):稱圖G是由H經過A-擴張而得，如果G是由H添加一條連通兩個不同點x，x'所得.

B-擴張(兩點擴張):設x∈V(H)，且dH(x)≥4.令H'=H{x→(b1，b2)}，使得dH'(b1≥2)，dH'(b2≥2).我們稱圖G是由H經過B-擴張而得，如果G是由H'經過添加一個新三度點a，使得a與b1，b2，w相連，這里w∈V(H-x)，見圖3.

C-擴張(三點擴張):設w∈V(H)，且dH(x)≥5.令H'=H{x→(b1，b2，b3)}，使得dH'(b1)≥2，dH'(b2)≥1，dH'(b3)≥2.我們稱圖G是由H經過C-擴張而得，如果G是由H'經過添加兩個新三度點a1，a2，使得a1與b1，b2相連，a2與b2，b3，相連，同時a1a2∈E(G)，見圖4.

圖2 Brick HFig.2 Brick H

圖3 點x擴張成b1，b2Fig.3 Expand x into b1，b2

圖4 點x擴張成b1，b2，b3Fig.4 Expand x into b1，b2，b3

圖5 點x，x'分別擴張成{b1，b2}，{b1'，b2'}Fig.5 Expand x into{b1，b2}，and x'into{b1'，b2'}respectively

D-擴張(兩個兩點擴張):設x，x'∈V(H)，且dH(x)≥4，dH(x')≥4.令H':=H{x→(b1，b2)，x'→(b'1，b'2)}，使得dH'(bi≥2)，dH'(bi'≥2)，i=1，2.我們稱圖G是由H經過D-擴張而得，如果G是由H'經過添加兩個新三度點a1，a2，使得a1與b1，b2相連，a2與b'1，b'2相連，同時a1a2∈E(G)，見圖5.

上述四種擴張過程中，圖H的那個被擴張的點叫做擴張點.Vx:={b1，b2，…，bk}中的每一個點都叫作由x分裂而得的分裂點.相應地，Vx就叫作點x對應的分裂點集.B-擴張后所得的點a和C-擴張(或者D-擴張)后所得的點a1，a2稱為G的相對于H的新點.

通過觀察可以發現，H中的每一條邊都可自然嵌入到G中.假設G，H都是Brick，且G是由H經過一次B-擴張、或C-擴張，或D-擴張而得到的Brick.不難看出，所以，B-擴張、C-擴張和D-擴張統稱為嚴格Brick-擴張而得.

定理1［6］假設H是一個Brick.如果圖G是由H經過一次Brick-擴張而得，那么G也是一個Brick.

定理2［6］每一個異于K4、以及Petersen圖的Brick都可由它們中的一個經過一系列Brick-擴張

2 主要結果

引理1 設H是一個Brick，G是一個極小Brick.如果G是由H經過一步嚴格Brick-擴張而得.如果H不是極小的，則存在一個非空邊子集E0?E(H)，使得H-E0是極小的，而且，E0中的每一條邊e都至少與H的一個擴張點相關聯，在G中那條與e相對應的邊至少有一個端點是三度分裂點.

證明 假設結論不成立.設e∈E0，e要么在H中不與任何一個擴張點相關聯，要么在G中，與其相對應的那條邊的兩個端點都不是三度分裂點.我們發現G-e能夠由H-e經過一次Brick-擴張而得，這個Brick-擴張就是那個從H得到G所運用的Brick-擴張.由定理1，G-e是一個Brick，與G是一個極小Brick矛盾.這樣就證明了這個引理.

推論1 設H是一個Brick，G是一個極小Brick.如果G是從H經過一步嚴格Brick擴張而得，記作K-擴張.如果H不是極小的，設E0?E(H)，使得H-E0是極小Brick.

證明 ①如果K=B，參考圖3，可以斷言，在E0中的每一條邊，在G中的對應邊都與同一個分裂點相關聯.

假設斷言不成立.由引理1，dG(b1)=dG(b2)=3.注意到a是G中相對于H的新點，又是分裂點b1和 b2的共同鄰點.所以dH-E0(x)≤2.但由假設H-E0是一個極小Brick，最小度大于等于3，矛盾.所以上述斷言成立.

不妨假設E0中的每一邊都與分裂點b1相關聯.由于dG(b1)=3，且a已經是b1的一個鄰點，所以≤2.

②如果K=C，參考圖4，可以斷言，E0在G中的對應邊集至多與兩個分裂點相關聯.

假設斷言不成立.由引理3，則dG(b1)=dG(b2)=dG(b3)=3.注意到a1，a2是G中相對于H的新點，且a1是分裂點b1和b2的共同鄰點，a2是分裂點b2和b3的共同鄰點.所以dH-E0(x)≤2.但由假設H-E0是一個極小Brick，最小度大于等于3，矛盾.所以上述斷言成立.

若E0中的邊都與同一個點bi相關聯，則≤2;若E0中的邊與兩個點bi，bj相關聯，則 E0≤4，得證.

如果K=D，參考圖5，同理可證.

定理3 極小Brick的點著色數小于等于4.

證明 采用歸納法來證明這個命題.很容易驗證三個基本Brick的點著色數小于等于4.由定理2，G可由其中一個基本Brick經過一系列Brick-擴張而得.記這個過程為G0→G1→…→Gk→Gk+1，其中，G0是其中一個基本Brick，Gk+1=G.由定理1，Gi都是Brick，i=1，2，…，k.因為G是極小Brick，所以G是由Gk經過一次嚴格擴張而得.

情況1:若Gk是極小Brick.根據歸納假設，Gk可以4著色.可以從Gk的一種4著色擴充成G一個4著色，其方案如下:對于那些非擴張點，保持顏色不變，對于Gk中的擴張點x，用Vx表示其相對應的分裂點集.不管這個嚴格擴張是哪一種類型，Vx中的點都著點x的顏色.而相對于Gk的新點都是三度點，總可以用第四種顏色著色.得證.

情況2:若Gk不是極小Brick.則存在一非空邊子集E0?E(Gk)，使得Gk-E0是一個極小Brick.由引理1，E0中的每一條邊e都至少與Gk的一個擴張點相關聯，在G中那條與e相對應的邊至少有一個端點是三度分裂點.根據歸納假設，Gk-E0可以4著色.我們可以從Gk-E0的一種4著色擴充成G的一個4著色，其方案如下:對于Vx中的非三度分裂點都著點x的顏色，而對于那些三度分裂點以及新點，總可以用第四種顏色著色，得證.