不包含｛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.