劉廣德

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

0 基本定義

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

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

1 主要定理

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

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

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

繼續(xù)往下畫時，第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)對應(yīng)的頂點數(shù)為7、8、9.

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

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

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

其中有2種情況加入1個剖分點后仍然需要4種顏色來染，這2種情況都是剖分點加在標(biāo)號為1的點對應(yīng)的邊上，因為在相同面上1的標(biāo)號沖突.

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

其中有6種情況加入1個剖分點后仍然需要4種顏色來染，這6種情況都是剖分點加在標(biāo)號為1和2的點對應(yīng)的邊上，因為在相同面上1和2的標(biāo)號都沖突.

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

其中有4種情況加入1個剖分點后仍然需要4種顏色來染，這4種情況都是剖分點加在標(biāo)號為2的點對應(yīng)的邊上，因為在相同面上2的標(biāo)號都沖突.

2 結(jié)論

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

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

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

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

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

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

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