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

方冬云

（莆田學院 數學學院，福建 莆田 351100）

0 引 言

文中用到的術語的相關符號參見文獻［1－2］，用到的相關知識參見文獻［3－6］。根據文獻［7］得G的極小反例的性質如下：

1）圖G是2－連通的，且圖G中沒有1－點。

2）圖G中的每個2－點都在C0上，且不與3－面相聯（推論：對任意v∈int（C0），d（v）≥3）。

3）C0不含弦。

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

5）圖G沒有一個四面體。

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

7）圖G不含一個3－面與一個3－面相鄰。

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

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

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

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

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

2）G中不含內部的6－面；

1 圖G不含分離的6－圈

設C是一個內部的非分離6－圈。則有：當｜C0｜＝10時，｜C∩C0｜≤3；當｜C0｜＝9，8或6時，｜C∩C0｜≤2；當｜C0｜＝3時，｜C∩C0｜≤1，且C與C0的公共點在C0上是連續的。

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

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

2）若｜C∩C0｜＝4。

設C∩C0＝x1x2x3x4。當x1x2x3x4在C0上是連續的，如果｜C0｜＝10，9，8，6時，則分別產生分離的10－圈、9－圈、8－圈和6－圈，這與不含｛4，5，7｝－圈平面圖的性質相矛盾。

設C∩C0＝x1x2x3x5，當x1x2x3x5在C0上是連續的，則x6與兩個鄰點x1，x5在C0，則｜C0｜＝4，與｜C0｜＝10矛盾。

設C∩C0＝x1x2x4x5，當x1x2x4x5在C0上是連續的，同樣得｜C0｜＝4，與｜C0｜＝10矛盾。所以｜C∩C0｜4。

3）若｜C∩C0｜＝3。

設C∩C0＝x1，x2，x3，當x1，x2，x3在C0上是連續的。如果｜C0｜＝9，8時，則產生分離的10－圈、9－圈，這與不含｛4，5，7｝－圈平面圖的性質相矛盾。如果｜C0｜＝6時，則產生7－圈，這與圖G本身的條件相矛盾。如果｜C0｜＝3時，則產生4－圈，這與圖G本身的條件相矛盾。

設C∩C0＝x1，x2，x4，當x1，x2，x4在C0上是連續的，則產生5－圈，這與圖G本身的條件相矛盾。

設C∩C0＝x1，x2，x5，當x1，x2，x5在C0上是連續的，則產生分離的10－圈，這與不含｛4，5，7｝－圈平面圖的性質相矛盾。所以｜C0｜＝10。

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

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

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

2 G不包含內部的6－面

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

3 f0不是一個6－面

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

4 結 語

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

［1］ 方 冬 云.不 包 含｛4，8，9｝－圈 的 平 面 圖 結 構 的 性 質［J］.長春工業大學學報：自然科學版，2011，32（5）：485－488.

［2］ 方 冬 云.不 包 含｛4，8，9｝－圈 的 平 面 圖 是3－可 染 的［J］.系統科學與數學，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.