劉廣德

(棗莊學(xué)院 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，山東 棗莊 277160)

0 基本定義

定義1:如果一個(gè)圖是可嵌入平面的，且它所有頂點(diǎn)出現(xiàn)在無(wú)窮面的邊界上，稱該圖為外平面圖.無(wú)窮面稱為外面，其余面稱為內(nèi)面［1］.

定義2:所有點(diǎn)出現(xiàn)在兩個(gè)面的邊界上的平面圖，稱為雙外平面圖，我們把這兩個(gè)面稱為外面［2］.

1 主要定理

定理1 雙外平面圖中只有一條路時(shí):當(dāng)頂點(diǎn)數(shù)為6n+k(n=1，2，...)(k=1，2，3)時(shí)，χv=4，否則 χv=3［3，4］.

證明 對(duì)于一條路從右向左按照1.2.3進(jìn)行標(biāo)號(hào)，如圖1所示:

圖1 8種結(jié)構(gòu)Fig.1 The 8 kinds of structure

繼續(xù)往下畫時(shí)，第9種結(jié)構(gòu)和圖1中的第3種一樣了，從上邊的8種結(jié)構(gòu)來看第1、2、3、4、5這5種結(jié)構(gòu)都可以用3種顏色來染色，第6、7、8這3種結(jié)構(gòu)都要用4種顏色來染色，第9種和第3種，第10種和第4種，第11種和第5種，第12種和第6種…都可以用一樣的顏色來染色，第6、7、8這3種結(jié)構(gòu)對(duì)應(yīng)的頂點(diǎn)數(shù)為7、8、9.

由此可以得出當(dāng)頂點(diǎn)數(shù)為6n+k(n=1，2，...)(k=1，2，3)時(shí)，χv=4，否則χv=3.證畢.

定理2:在雙外平面圖中只有一條路，且χv=4時(shí)，當(dāng)在相同面上兩端的頂點(diǎn)標(biāo)號(hào)沖突時(shí)，如果剖分點(diǎn)加在這個(gè)標(biāo)號(hào)相對(duì)的邊上時(shí)，仍然有 χv=4，否則 χv=3［5－6］.

證明:(1)對(duì)于圖1中的第6種結(jié)構(gòu)加入1個(gè)剖分點(diǎn)有如下圖2的情況.當(dāng)我們可以重新進(jìn)行進(jìn)行標(biāo)號(hào)，有的可以用3種顏色進(jìn)行染色，結(jié)果如圖3所示

其中有2種情況加入1個(gè)剖分點(diǎn)后仍然需要4種顏色來染，這2種情況都是剖分點(diǎn)加在標(biāo)號(hào)為1的點(diǎn)對(duì)應(yīng)的邊上，因?yàn)樵谙嗤嫔?的標(biāo)號(hào)沖突.

(2)對(duì)于圖1中的第7種結(jié)構(gòu)加入1個(gè)剖分點(diǎn)有如圖4的情況.我們可以重新進(jìn)行進(jìn)行標(biāo)號(hào)，有的可以用3種顏色進(jìn)行染色，結(jié)果如圖5所示:

其中有6種情況加入1個(gè)剖分點(diǎn)后仍然需要4種顏色來染，這6種情況都是剖分點(diǎn)加在標(biāo)號(hào)為1和2的點(diǎn)對(duì)應(yīng)的邊上，因?yàn)樵谙嗤嫔?和2的標(biāo)號(hào)都沖突.

(3)對(duì)于圖1中的第8種結(jié)構(gòu)加入1個(gè)剖分點(diǎn)有如圖6情況.我們可以重新進(jìn)行進(jìn)行標(biāo)號(hào)，有的可以用3種顏色進(jìn)行染色，結(jié)果如圖7所示:

其中有4種情況加入1個(gè)剖分點(diǎn)后仍然需要4種顏色來染，這4種情況都是剖分點(diǎn)加在標(biāo)號(hào)為2的點(diǎn)對(duì)應(yīng)的邊上，因?yàn)樵谙嗤嫔?的標(biāo)號(hào)都沖突.

2 結(jié)論

由上邊的3種χv=4加一個(gè)剖分點(diǎn)的結(jié)果，有以下結(jié)論:當(dāng)在相同面上兩端的頂點(diǎn)標(biāo)號(hào)沖突時(shí)，如果剖分點(diǎn)加在這個(gè)標(biāo)號(hào)相對(duì)的邊上時(shí)，仍然有χv=4，加在其他邊上時(shí)，有χv=3.另在第8種結(jié)構(gòu)時(shí)，當(dāng)剖分點(diǎn)加在相同面上兩端的頂點(diǎn)標(biāo)號(hào)不沖突的邊上，仍然有χv=4.證畢.

［1］JA，默帝 USR.圖論及其應(yīng)用［M］.北京:科學(xué)出版社，1984.

［2］孔立.一個(gè)特殊雙外平面圖的全染色［J］.洛陽(yáng)大學(xué)學(xué)報(bào).2005，20(2):7－9.

［3］陳東靈，吳建良.外平面圖的一個(gè)結(jié)構(gòu)定理［J］.山東科技大學(xué)學(xué)報(bào).1999，18(4):41－43.

［4］張?zhí)K梅.外平面圖的 L(d，1)－標(biāo)號(hào)［J］.濟(jì)南大學(xué)學(xué)報(bào)(自然科學(xué)版).2006，20(3):258－260.

［5］孔立.雙外平面圖的全染色［J］.山東輕工業(yè)學(xué)院學(xué)報(bào).2005，19(2):81－84.

［6］孔立.雙外平面圖的邊面染色［J］.煙臺(tái)師范學(xué)院學(xué)報(bào)(自然科學(xué)版).2005，21(2):106－108.