不包含｛4，8，9｝－圈平面图结构的性质

方冬云

（莆田学院 数学系，福建 莆田 351100）

1 基本术语及符号［1］

图论一个偶对G＝（V，E）来定义图，其中V表示顶点的集合，E表示边的集合，如果图G中边的两个顶点是无序的，则称图G为无向图。一般图G＝（V，E）的顶点数用｜V｜表示，边的数目用｜E｜表示，如果｜V｜和｜E｜都是有限的，则称图G是有限无向图，如果图G既没有环也没有两条连杆连接同一对顶点，则称图是简单图，文中所研究的图均指的是有限简单无向图。有限简单无向图G中的顶点u和v，若边e＝uv∈E（G），则称u和v相邻，也称u和v是e的端点，u和v分别与e相关联，则称u为图G中的任一顶点，与顶点u关联的边数称为u的度数，记作dG（u）。

如果有限简单无向图G能画在曲面上，且除端点处之外任何两条边均不相交，则称图G被嵌入曲面上，如果图G可以被嵌入在平面上，称为是可平面图，已经被嵌入在平面上的图称为平面有限简单无向图。设u和v是图的顶点，图G的一条u－v途径（链）是有限非空的顶点和边交替序列W＝u0e1u2e3…un－1enun（u＝u0，v＝vn），其中与边ei（1≤i≤n）相邻的两顶点ui－1和ui正好是ei的两个端点，如果w上的顶点互不同的途径称为路记作Pi，u0，ui分别为Pi的起点和终点，起点和终点相同的路称为圈。

图G的一个k－染色是一个映射φ：V→｛1，…，k｝，使得φ（u）≠φ（v），其中uv∈E。这样的映射称图G为k－可染。如果G有一个k－染色，令H是图G的一个点导出子图，φ是H 的一个k－染色，若G有一个k－染色φ，且满足φ在H 上的限制正好是φ，则称φ是φ在图G上的一个延拓，或称φ可以延拓到图G上。

令C是图G的一个圈，分别记圈C内部和外部的点集为int（C）和ext（C）。显然，Int（C）＝G－ext（C）和Ext（C）＝G－int（C）是图G的两个点导出子图。连接一个圈上不相邻两点间的连线称为弦，注意，在C内部的C的弦属于Ext（C）。若恒有int（C）≠Φ且ext（C）≠Φ，则称C为分离圈。否则称C是一个非分离的圈。

2 一些平面图研究成果的简介

平面有限简单无向图（简称平面图）的点染色问题起源于著名的四色猜想，接着，人们试着对4－可选择的平面图作了一些特征刻画，且关于2－可选择这样的问题，Erdos［2］等人已经做了特征化的论述，因此，许多学者对平面图3－可染（可选择）问题做了一系列的讨论与研究：

存在一个常数k＊，使得不包含｛4，5，…，K＊｝－圈的平面图是3－可染的［3］；不包含｛4，5，…，9｝圈的平面图是3－可染的［4］；每个不包含｛4，6，8.9｝－圈的平面图是3－可选择的［5］；每个不包含｛4，6，8｝－圈的平面图是3－可染的［6］；每个不包含｛4，7，9｝－圈的平面图是3－可染的［7］；每个不包含｛4，6，9｝－圈的平面图是3－可染的［8］；根据这些研究的成果，进一步分析不包含｛4，8，9｝－圈的平面图结构性质。

3 不包含｛4，8，9｝－圈平面图结构的性质

要证明这7个性质，需要介绍一个定义，即不包含｛4，8，9｝－圈平面图G 的极小性：设f0为图G中的一个i面，i∈｛3，5，6，7，10，11｝，G［V（f0）］有一个3－染色φ，但φ不可延拓到整个图G上。

不包含｛4，8，9｝－圈平面图G 具有如下性质：

1）C0不含弦。即：若v∈V（C0），d（v）≥3，则v有且仅有两个邻点在C0上；

2）G是2－连通的，G中的任意面的边界都是一个圈；

3）对任意v∈int（C0），d（v）≥3；

4）G不含长度为≤11的分离圈；

5）G中的内部非分离6－圈不含弦，且不与3－圈相邻；

6）G中没有包含非三角弦的10－圈和11－圈；

7）G中的内部非分离6－圈不与5－圈相邻。

证明：

1）假若uv为C0上的一条弦。从G中删去uv，得新图记为G′，则 w（G′）≤w（G），σ（G′）＜σ（G）。显然G′仍是一个连通的平面图。则由G的极小性知，φ可延拓到G′上。由于φ是G［V（f0）］的一个3－染色，故φ（u）≠φ（v）。从而得到φ可延拓到G上，即图G是3－可染的，与图G的极小性矛盾。故C0不含弦。若v∈V（C0），d（v）≥3，则由C0不含弦，根据定义v有且仅有两个邻点在C0上。

2）假若图G有一个割点v连接两个块B1和B2＝G－（V（B1）＼｛v｝）。显然，块Bi，i＝1，2，仍是不包含｛4，8，9｝－圈的连通平面图，且w（Bi）≤w（G），σ（Bi）＜σ（G）。若C0是B1，B2的外部面边界的并集，则由G的极小性知，C0的3－染色可分别延拓到B1和B2上，从而得到G的一个3－染色，与图G的极小性矛盾。否则，若C0不是B1，B2的外部面边界的并集，则C0⊆B2。由G的极小性知，C0的3－染色可延拓到B2上。若B1是3－可染的，适当交换B1中点的染色，使v在B1中的染色与其在B2中的一致，则可得到G的一个3－染色，与图G的极性矛盾。下面我们只需证B1确实是3－可染的。

若B1不含6－圈，则由文献［5］中所证明的每个不包含｛4，6，8，9｝－圈的平面图是3－可选择的，得B1是3－可染的；若B1至少包含一个6－圈C，由于图G不含4－圈，8－圈，故C至多只有一条弦。故C有一个3－染色，由G的选取知，C的3－染色可分别延拓到B1中C的外部和内部上，即B1是3－可染的。

3）假若v∈int（C0），d（v）≤2。记从图G 中删去顶点v得到的新图为G′，则w（G′）≤w（G），且σ（G′）＜σ（G），G′仍为连通的平面图。由G 的选择，φ可延拓到G′上，由于d（v）≤2，故易对v染色，从而得到G的一个3－染色，与图G的极小性矛盾。

4）假若G中存在这样的分离圈Ci，｜Ci｜≤11。显然，i∉｛4，8，9｝，则由G 的极小性，φ可延拓到ext（Ci）上，i∈（3，5，6，7，10，11｝。由G 的极小性知，去掉Ci中的可能弦，可将φ在Ci上的限制延拓到int（Ci）上，从而G是3－可染的，与图G的选择矛盾。

5）假若G中有一个内部的非分离6－圈C＝u0u1u2u3u4u5u0，且C含弦xy。由于G不含4－圈，故可设xy＝u1u5时：若v0是内部点，则圈u1u0u5u1在图中是一个分离的3－圈，与性质4）结论矛盾；若u0不是内部点，则u1u2u3u4u5u1在图中是一个分离的5－圈，与性质4）结论矛盾，故G中的内部非分离6－圈不含弦。如图1所示。

图1 内部含非分离6－圈的平面图

由于图G中的内部非分离6－圈不含弦，所以G中与内部非分离3－圈只可能是一般相邻，设图G中存在与内部非分离的6－圈一般相邻的3－圈，如图2所示。

图2 非分离6－圈与3－圈相邻的平面图

此时所得的新图记为G′，删去弦xy，适当调整染色，可使x，y染不同的颜色，则可得G是3－可染。由G的选取可知，φ可延拓到G′上，从而得到φ可延拓到G上。与图G的极小性矛盾，故G中的内部非分离6－圈不与3－圈相邻。

6）假若图G中有一个含非三角弦e的圈C11。由于图G 中不含4－，8－，9－圈，故弦e只能把C分成一个C5和一个C6。如果int（C5）和int（C6）都是空集的话，那么去掉这条非三角弦，C0的染色φ可延拓到去掉弦后的新图G′上，φ从而可延拓到图G 上，与图G的极性矛盾。如果int（C5）和int（C6）至少一个非空的话，则可得到分离的5－圈或分离的6－圈，与性质4）结论矛盾。图G中有一个含非三角弦e的圈10－圈的情形类似证明。

7）先证：若G中的内部非分离6－圈与5－圈是相邻的，也只可能是一般相邻的。设C5＝xyv1v2v3x和非分离6－圈C6＝xyu1u2u3u4x是相邻的，如图3所示。

图3 非分离6－圈与5－圈相邻的平面图

首先v1∉V（C6）：若v1＝u1，y是内部点，则xv3v2v1yx在图中是一个分离的5－圈，与性质4）结论矛盾；若y不是内部点，则xv3v2u1u2u3u4x在图中是一个分离的7－圈，与性质4）结论矛盾；若v1∈｛u2，u3，u4｝，则与内部非分离6－圈不含弦矛盾；由对称性可知，v3∉V（C6）；其次v2∉V（C6）：若v2＝u1，则会产生一个4－圈u1yxv3u1，与不包含｛4，8，9｝－圈的平面图条件矛盾；若v2＝u2，则会产生一个4－圈u2u1yv1u2，与不包含｛4，8，9｝－圈的平面图条件矛盾；若v2＝u3，则会产生一个4－圈u2u4xv3u3，与不包含｛4，8，9｝－圈的平面图条件矛盾；由对称性得，v2≠u4。

但是内部非分离6－圈与5－圈不可能是一般相邻的，否则会产生一个含非三角弦的11－圈。

4 结 语

根据文献［5］给出了定理：每个不包含｛4，6，8，9｝－圈的平面图是3－可选择的。尝试将6－圈的条件去掉，研究不包含｛4，8，9｝－圈的平面图结构的一些性质，这些性质为研究“每个不包含｛4，8，9｝－圈的平面图是3－可染的”的命题提供了前提依据。

［1］J Yin，K Wu.Theory and its algorithm［M］.Hefei：China University of Science and Technology，2003.

［2］P Erdos，A L Rubin，H Taylor.Choosability in graphs［J］.Congr Numer，1979，26：125－157.

［3］R Steinberg.The state of the three color problem［J］.Diserete Math.，1993，55：211－248.

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

［5］L Shen，Y Q Wang.A sufficient condition for aplanar graph to be 3－choosable［J］.Inform Process Lett，2007，104：146－154.

［6］W Wang，M Chen.Planar graphs without 4，6and 8－cycles are 3－colorable［J］.Sci.China Ser AMath.，2007，50（11）：1552－1562.

［7］H Lu，Y Wang，W Wang，et al.On the 3－colorability of planar graphs without 4－，7－and 9－cycles［J］.Discrete Mathematics，2009，309：4596－4607.

［8］D Liao.On the 3－colorability of planar graphs without 4－，6－and 9－cycles［D］：［Master’s Degree Thesis］.Fuzhou：Fuzhou University，2010.