不包含｛4，5，7｝圈的平面圖是3－可染的延拓性定理

方冬云

（莆田學(xué)院 數(shù)學(xué)學(xué)院，福建 莆田 351100）

0 引 言

文中用到的術(shù)語的相關(guān)符號參見文獻(xiàn)［1－2］，用到的相關(guān)知識參見文獻(xiàn)［3－6］。根據(jù)文獻(xiàn)［7］得G的極小反例的性質(zhì)如下：

1）圖G是2－連通的，且圖G中沒有1－點(diǎn)。

2）圖G中的每個(gè)2－點(diǎn)都在C0上，且不與3－面相聯(lián)（推論：對任意v∈int（C0），d（v）≥3）。

3）C0不含弦。

4）圖G不含長度≤10的分離圈，且每個(gè)分離的11－圈是一個(gè)獨(dú)立面。

5）圖G沒有一個(gè)四面體。

6）圖G中的內(nèi)部非6－圈不含弦，且不與3－圈相鄰。

7）圖G不含一個(gè)3－面與一個(gè)3－面相鄰。

8）圖G不含一個(gè)3－面與4－面相鄰。

延拓性定理：設(shè)圖G是一個(gè)不包含｛4，5，7｝－圈的連通平面圖，若f是G中的一個(gè)i－面，i∈｛3，6，8，9，10｝，則G［V｛f｝］的任意一個(gè)3－染色都可延拓到整個(gè)圖G上（其中V（f）指的是面f的邊界點(diǎn)依順時(shí)針方向排列）。

證明：（反證）設(shè)圖G為這個(gè)延拓性定理的極小反例，設(shè)w（G）為圖G中6－圈的個(gè)數(shù)，σ（G）＝｜V｜＋｜E｜，w（G）和σ（G）要盡可能的小。設(shè)f0為圖G中 的 一 個(gè)i－面，i∈｛3，6，8，9，10｝，G［V（f0）］有一個(gè)3－染色φ，但φ不可延拓到整個(gè)圖G上。不失一般性，假若f0是G中的一個(gè)無界面，C0＝b（f0）是f0的邊界。

為了得出矛盾，只需證明G中不含6－圈，要得到這個(gè)延拓性定理的證明，可分3個(gè)步驟：

1）G中不含分離的6－圈；

2）G中不含內(nèi)部的6－面；

1 圖G不含分離的6－圈

設(shè)C是一個(gè)內(nèi)部的非分離6－圈。則有：當(dāng)｜C0｜＝10時(shí)，｜C∩C0｜≤3；當(dāng)｜C0｜＝9，8或6時(shí)，｜C∩C0｜≤2；當(dāng)｜C0｜＝3時(shí)，｜C∩C0｜≤1，且C與C0的公共點(diǎn)在C0上是連續(xù)的。

證明：首先由于C0不含弦，故｜C∩C0｜≤5，且C與C0的公共點(diǎn)若在C上是連續(xù)的，則在C0上也是連續(xù)的。令C＝x1x2x3x4x5x6x1。

1）若｜C∩C0｜＝5。不妨設(shè)x6∈C且x6?C0，則x1和x5是x6在C0上的兩個(gè)鄰點(diǎn)，從而得｜C0｜＝5，與｜C0｜＝10矛盾。所以｜C∩C0｜5。

2）若｜C∩C0｜＝4。

設(shè)C∩C0＝x1x2x3x4。當(dāng)x1x2x3x4在C0上是連續(xù)的，如果｜C0｜＝10，9，8，6時(shí)，則分別產(chǎn)生分離的10－圈、9－圈、8－圈和6－圈，這與不含｛4，5，7｝－圈平面圖的性質(zhì)相矛盾。

設(shè)C∩C0＝x1x2x3x5，當(dāng)x1x2x3x5在C0上是連續(xù)的，則x6與兩個(gè)鄰點(diǎn)x1，x5在C0，則｜C0｜＝4，與｜C0｜＝10矛盾。

設(shè)C∩C0＝x1x2x4x5，當(dāng)x1x2x4x5在C0上是連續(xù)的，同樣得｜C0｜＝4，與｜C0｜＝10矛盾。所以｜C∩C0｜4。

3）若｜C∩C0｜＝3。

設(shè)C∩C0＝x1，x2，x3，當(dāng)x1，x2，x3在C0上是連續(xù)的。如果｜C0｜＝9，8時(shí)，則產(chǎn)生分離的10－圈、9－圈，這與不含｛4，5，7｝－圈平面圖的性質(zhì)相矛盾。如果｜C0｜＝6時(shí)，則產(chǎn)生7－圈，這與圖G本身的條件相矛盾。如果｜C0｜＝3時(shí)，則產(chǎn)生4－圈，這與圖G本身的條件相矛盾。

設(shè)C∩C0＝x1，x2，x4，當(dāng)x1，x2，x4在C0上是連續(xù)的，則產(chǎn)生5－圈，這與圖G本身的條件相矛盾。

設(shè)C∩C0＝x1，x2，x5，當(dāng)x1，x2，x5在C0上是連續(xù)的，則產(chǎn)生分離的10－圈，這與不含｛4，5，7｝－圈平面圖的性質(zhì)相矛盾。所以｜C0｜＝10。

4）若｜C∩C0｜＝2。由于圖G上不含弦，所以這兩個(gè)公共頂點(diǎn)在C0上是連續(xù)的。如果｜C0｜＝3時(shí)，則產(chǎn)生5－圈或4－圈，這與圖G本身的條件相矛盾。故｜C0｜3。

如果｜C0｜＝10時(shí)，由于圖G上不含弦，所以C∩C0的兩個(gè)頂點(diǎn)不能相鄰，但兩個(gè)頂點(diǎn)在C0是連續(xù)的。設(shè)C∩C0＝x1x3，則產(chǎn)生分離的6－圈，這與不含｛4，5，7｝－圈平面圖的性質(zhì)相矛盾。設(shè)C∩C0＝x1x4，則產(chǎn)生分離的10－圈，這與不含｛4，5，7｝－圈平面圖的性質(zhì)相矛盾。故｜C0｜3，綜上所述，｜C0｜＝9，8或6。

5）若｜C∩C0｜＝1時(shí)，當(dāng)｜C0｜≥6，則｜C0｜＞10，這與圖G本身的條件相矛盾。故｜C0｜＝3。所以圖G不含分離的6－圈。

2 G不包含內(nèi)部的6－面

假設(shè)圖G有一個(gè)內(nèi)部的6－面f＝u0u1u2u3u4u5，不失一般性，可設(shè)d（u0）≥3，即u0有一個(gè)不同于u1，u5的鄰點(diǎn)設(shè)為v0。記H為合并圖G中的頂點(diǎn)u1和u5，u2和u4后形成的圖，合并后得到的點(diǎn)分別記為w1，w2。根據(jù)文獻(xiàn)［2］，不含｛4，8，9｝－圈的平面圖不含內(nèi)部的6－面的證明，可以類似得圖G不含內(nèi)部的6－面。

3 f0不是一個(gè)6－面

設(shè)f0是一個(gè)6－面，由于圖G不含4－圈、5－圈、7－圈，不失一般性，在它的一條邊上插入4個(gè)2－點(diǎn)，記所得到的新圖為G′，則G′仍是一個(gè)連通的平面圖。且圖G′不含4－圈，由于圖G是簡單圖。所以圖G′中不存在含新邊的6－圈，因此f0不是一個(gè)6－面。

4 結(jié) 語

圍繞圖G中不含分離的6－圈、圖G中不含內(nèi)部的6－面及｜f0｜6三個(gè)步驟，證明這個(gè)延拓性定理：設(shè)圖G是一個(gè)不包含｛4，5，7｝－圈的連通平面圖，若f是G中的一個(gè)i－面，i∈｛3，6，8，9，10｝，則G［V（f）］的任意一個(gè)3－染色都可延拓到整個(gè)圖G上。從而也證明了每個(gè)不包含｛4，5，7｝－圈的平面圖是3－可染的。

［1］ 方 冬 云.不 包 含｛4，8，9｝－圈 的 平 面 圖 結(jié) 構(gòu) 的 性 質(zhì)［J］.長春工業(yè)大學(xué)學(xué)報(bào)：自然科學(xué)版，2011，32（5）：485－488.

［2］ 方 冬 云.不 包 含｛4，8，9｝－圈 的 平 面 圖 是3－可 染 的［J］.系統(tǒng)科學(xué)與數(shù)學(xué)，2012，32（9）：1155－1165.

［3］ R Steinberg.The state of the three color problem.In：J Gimbel，J W Kenndy，eds.Quo Vadis，Graph Theory［J］.Diserete Math.，1993，55：211－248.

［4］ H L Abbott，B Zhou.On small faces in 4－critical graph［J］.Ars Combin，1991，32：203－207.

［5］ O V Borodin.Structural properties of plane graphs without adjacent triangles and an application to 3－colroings［J］.J.Graph Theory，1996，21（2）：183－186.

［6］ D P Sanders，Y Zhao.A note on the three coloring problem［J］.Graphs Combin，1995，11：92－94.

［7］ M Montassier，A Raspaud，W Wang.Bordeaux 3－color conjecture and 3－choosability［J］.Discrete Math.，2006，306：573－579.