平面图3可着色的一个充分条件

赵春红

（沙洲职业工学院建筑工程系，江苏张家港215600）

平面图3可着色的一个充分条件

赵春红

（沙洲职业工学院建筑工程系，江苏张家港215600）

为研究平面图的3着色问题，运用文献[1]中权转移的方法证明了一类平面图3可着色的一个充分条件，即：不含5-圈，且每个4-圈，6-圈或7-圈不与长度小于8的圈有公共边的平面图是3-可着色的。

平面图；圈；着色

图的点着色问题[2]一直是图论学者研究的热点，从四色问题的提出，到著名五色定理，最后学者们把点着色的研究重点放在平面图的3着色上，出现很多猜想，得到很多结论。针对Erdös提出的关于平面图3着色的猜想（是否存在整数k，使得每个不含4至k圈的平面图是3-可着色的），无数图论学者都致力于把这个未知数k降低到最小：1991年，Abbott和Zhou把k降低到了11，2005年Borodin和Raspaud等人把k降低到了7，目前更小的k值还未得到证明。笔者通过增加一些附加条件，在文献[3]中证明了两个结论：（1）每一个不含4-6圈，也不含距离小于2的三角形对，且每个7-圈最多与一个三面相邻的平面图是3-可着色的；（2）每一个不含4-圈和5-圈，且每个6-圈或7-圈不与长度小于8的圈有公共边的平面图是3-可着色的。在该文中，所研究的图为有限简单图，除特别定义外，所使用的术语、概念、符号都与文献[2]中一致。

设Γ是不含5-圈，且每个4-圈，6-圈或7-圈不与长度小于8的圈有公共边的平面图集合。笔者将继续运用权转移的方法，在文中证明：

定理1∀G∈Γ，χ（G）≤3，其中χ（G）为G的色数。

要证明此结论，需要先讨论一类极小平面图的结构及其存在性。

1 一类极小平面图的结构讨论

假设存在G∈Γ，是一个边数和点数之和|E（G）|+|V（G）|=δ（G）最少的且存在G中的某一个4-圈或长为6至11的圈f0的边界D的导出子图的3-着色φ不可扩充到整个图G的极小平面图。笔者在文献[4]中已经证得图G的以下8个结论：

（1）G中不含有长度小于等于11的分离圈S。

（2）G中圈长为4、6至8的圈不含有弦，圈长为9至11的圈不含有非三角形的弦。

（3）D是一个简单圈，无弦。

（4）G是2连通的。

（5）G的每一个2度点都属于D，且没有一个2度点与一个3面相关。

（6）G中的6-圈或7-圈都不与三角形有公共边。

（7）除f0外，任何两个面都不可能正好拥有两条相邻的公共边。

（8）G中无四元组。

根据已有结论，D在G中界定一个面，不妨设f0为圈D界定的面且为G的外部面，若G含有内部4-圈，则该4-圈一定是4-面。由文献[5]，可证明以下结论。

引理1G不含有内部4-面。

证明假设G中含有内部4-面f，其边界为T=uvwxu，则f不可能与长度小于8的圈有公共边。f也不可能与长度为9的圈有两条相邻的公共边。否则，设有两条相邻的公共边uv，vw，则v点的度不可能是2，否则G是3-可着色的。因此，在该9-圈内部存在一点v′是v的邻点，而该9-圈就分离了v′和x，与8个结论中的结论（1）矛盾。

设Guw表示粘合u和w得到的平面图，Gvx表示粘合v和x得到的平面图，则：

（1）Guw不含有5-圈，否则在G中会产生4-圈与7-圈有公共边的情形，与G的选取矛盾。

（2）若粘合u和w得到的平面图Guw不会产生新的3-圈、4-圈、6-圈和7-圈，则由G的选取，显然Guw是3可着色的，从而得到G的3着色，矛盾。

（3）粘合u和w得到的平面图Guw不会产生新的3-圈、4-圈，否则在G中会产生4-圈与6-圈有公共边的情形，与G的选取矛盾。

以上（1）、（2）、（3）对于Gvx同样成立。

（4）从而，不妨设粘合u和w得到的平面图Guw会产生新的6-圈和7-圈，且粘合v和x得到的平面图Gvx也会产生新的6-圈和7-圈。

因此，存在一条路p1连接u和w，一条路p2连接v和x，其中p1、p2的长度为6或7。由于G是平面图，则p1{u，w}，p2{v，x}有一个公共点。但V（p1）∩{v，x}=Φ，V（p2）∩{u，w}=Φ。否则，在G中会出现f与某个长度小于8的圈有公共边的情况，与G的选取矛盾。设P1=ub1b2b3bl1-1，（l1=5，6），且假设bi∈{V（pi）}为p1、p2的唯一公共点。设对于每一条路p和p上的不同点u、w，用p[u，w]表示p中连接u、w的一部分路。设pu=p1[u，bi]，pw= p1[bi，w]，pv=p2[v，bi]，px=p2[bi，x]，对于s∈{u，v，w，x}，设ls表示路ps的长度，则由G的选取，有

通过计算可以发现，这个方程组无解。因此，平面图Guw和Gvx中至少有一个不会产生新的6-圈和7-圈。

假设Guw不会产生新的6-圈和7-圈。综合以上讨论，Guw⊆Γ，且为比G的边少的平面图，因此，如果粘合u、w得到的平面图Guw没有破坏D的着色的话，则可以把D的着色扩充到Guw，从而扩充到G，矛盾。

现在证明D的着色φ不会被粘合u和w所破坏。若被破坏，则意味着粘合u和w出现了两种结果：（a）粘合了D中着以不同颜色的点；（b）把D中着相同颜色的两个点连成边。总之，这两种情况都说明了u和w到D的距离之和最多为1。

设D=d1d2…d|D|，按照顺时针顺序递增排列，设d|D|是D中离u最近的点，而dj是离w最近的点，因为|D|≤11，所以D被dj和d|D|分成两条路P1，P2，设P1＝d|D|d1…dj，至多有5条边，这条路与路djuv3v2v1wd|D|相关，产生一个圈长至多为11的圈C，矛盾。

因此，G中不含有内部4-面。

2 极小平面图G的存在性讨论

关于极小平面图G的存在性讨论如下：

（1）若f0≠4，则G为不含有4-圈和5-圈，且每个6-圈或7-圈都不与长度小于8的圈有公共边的平面图，由文献[3]可知，G是3-可着色的，矛盾。

（2）若f0＝4，下面将用权转移的方法证明极小平面图G不存在。

不要将教师摆在一个主导学生的地位，要把自己放在与学生平等的位置，和学生共同学习，共同进步.课堂上要把尽量多的时间留给学生，减少讲课的时间，引导学生自主学习，如：我们在就学习《命题及其关系》这一部分时，我们用2课时进行学习，其中第一课时时我们只抽出15分钟时间来讲解基础知识，其余时间交给学生，可以让学生来讲解一部分知识或题目，让学生提出问题并让其他学生来回答，老师进行纠正;在第二课时时，老师可以对大部分学生不能理解的内容重点讲解，然后让学生讨论本节的收获，整理重难点.这种教学理念也可以帮助学生转变自己的思维方式，使自己的数学思维更加发散.

对于∀x∈（V（G）∪F（G））{f0}，令w（x）=d（x）-4，对于f0，令w（x）=d（x）+4。由Euler公式|V（G）|-|E（G）|+ |F（G）|=2，得。

定义权转移规则如下：

R1：每一个三面从其相关点处收获1/3；

R2：v是与内部非三角形面f相关的顶点：（a）设d（v）=2，则f给予v点2/3；（b）设d（v）=3，且v是内部点：若v是坏点，则f给予v点2/3，否则f给予v点1/3；（c）设d（v）≥4：若v是内部点且v不与3-面相关，则f给予v点1/3；若v是内部点，v与3-面相关，且f与这个3-面相邻，则f给予v点1/3；若v是外部点，v与3-面相关，但f与这个3-面不相邻，f从v点收获1/3；

R3：外部面f0给D的每个点4/3。

记每一个元素的新权重为w*（x），其中x∈V（G）∪F（G）。

引理2∀v∈V（G），w*（v）≥0。

d（v）=3，若v是外部点，则至多与一个三面相关，由R3，v可从外部面得到4/3，由R1，只要给予相关三面1/3，w*（v）≥3-4+4/3-1/3=0；若v是内部点，如果v是坏点，则与v相关的面中必有两个非三角形的面，由R1，R2，w*（v）≥3-4+（2/3）×2-1/3=0，如果v不是坏点，由R2，w*（v）≥3-4+（1/3）×3=0。

d（v）=4，若v是外部点，如果v与一个三面相关且三面与D相邻，则与v相关的另外两个面中一个与三面相邻，一个与三面不相邻，由R3，一个面既无收获也不给予，一个给予f面1/3，则w*（v）=4-4+4/3-1/3-1/3＞0；如果v与一个三面相关且三面不与D相邻，则与v相关的另外两个面既无收获也不给予，w*（v）=4-4+4/3-1/3＞0；如果v不与三面相关，由R3，w*（v）=4-4+4/3＞0；若v不是外部点，如果v与一个三面相关，由R1，v要给予相关三面1/3，而与v相关的面中除这个三面外必有三个非三角形的面，其中两个与三面相邻，一个不与三面相邻，由R3，一个面既无收获也不给予，两个面给予v点各1/3，则w*（v）=4-4-1/3+（1/3）×2＞0，如果v不与三面相关，w*（v）=4-4=0。

d（v）=5，若v是内部点，由R1和R3，v至多给两个三面1/3，同时至多给一个非三面1/3，w*（v）≥5-4-（1/3）×3=0；若v是外部点，由R1和R3，w*（v）≥5-4+4/3-（1/3）×5＞0。

d（v）≥6，由R1和R3，v至多给d（v）个1/3，w*（v）≥d（v）-4+d（v）×（1/3）≥0。

引理3w*（f0）＞0。

证明由f0=4，w*（f0）=d（f0）+4-d（f0）×（4/3）＞0。

引理4∀f≠f0，w*（f）≥0。

证明d（f）=3，由R1，w*（f）=3-4+3×（1/3）=0。

d（f）＞8，若f与一个2度点v相邻，显然，由R2，f给予v点2/3，且f与D相关的公共点中有2个点的度大于等于3，这2个点也是D边界上2度点形成的最大路径的端点，且这2个点从面既不给予也不收获，设由这2个点划分的D边界上的另一段路径为P，且最多P上的每个点的度都为3，且都与一个三角形相邻，则w*（f）=d（f）-4+（d（f）-2）×（2/3）≥0。

d（f）=6或d（f）=7，若f与一个2度点v相邻，显然，v∈D，则会出现4-圈与6-圈或7-圈有公共边的情况，矛盾。故，以下总假设非外部面上没有2度点。设d（f）=6，由于G中的6-面不与三面相邻，则f最多给予每个点1/3，则w*（f）≥6-4-6×（1/3）=0，设d（f）=7，由于G中的7-面不与三面相邻，则f最多给予每个点1/3，则w*（f）≥7-4-7×（1/3）＞0。

d（f）=8，分下列情况讨论：

（1）若f给其至少4个点最多都是1/3，或者至少有2个点从f处既不收获也不给予，则w*（f）≥8-4-4×（2/3）-4×（1/3）≥0，或者w*（f）≥8-4-6×（2/3）≥0。

（2）若f中有一个点v∈D，则该点不是坏点，d（v）≥3。若d（v）=3，则该点从f处既不收获也不给予，且f中与v相邻的点中也有一个点属于D，加上其他的6个点不可能都是坏点，w*（f）≥8-4-5×（2/3）-2×（1/3）≥0；若d（v）≥4，且v不与三面相关，则该点从f处既不收获也不给予，而其他7个点至少有2个点不是坏点，w*（f）≥8-4-5×（2/3）-2×（1/3）≥0，若v与三面相关分以下情况讨论：（i）f与三面不相邻，则f从v收获1/3，而另外7个点不可能都是坏点，则w*（f）≥8-4-6×（2/3）-1/3+1/3≥0；（ii）f与三面相邻，则点v既无收获也不给予，而另外7个点不可能都是坏点。若有6个坏点，必有4个三角形与f相邻，另一点u，必然d（u）≥4，则由R2，f从v收获1/3，则w*（f）≥8-4-6×（2/3）+1/3≥0，若有5个坏点，则另2个点最多从f面收获1/3，则w*（f）≥8－4-5×（2/3）-2×（1/3）≥0，若只有4个及其以下坏点，则w*（f）≥8－4-4×（2/3）-4×（1/3）≥0。

（3）不妨设f中的点都不属于D，且或者有6个坏点，或者有5个坏点。若f有6个坏点，则f必然与四个三面相邻，则另2个点的度大于等于4，则这2个点给予f面1/3，则w*（f）≥8－4-6×（2/3）+2×（1/3）≥0；若f有5个坏点，或者f与四个三面相邻，则另3个点的度大于等于4，则这3个点给予f面1/3，则w*（f）≥8－4-5×（2/3）+3×（1/3）≥0，或者f与三个三面相邻，则相关的6个点中必有1个点的度大于等于4，则该点给予f面1/3，则w*（f）≥8－4-5×（2/3）-2×（1/3）+1/3≥0。

d（f）＝9，由于f最多可与4个三角形相关，但由于G无四元组，所以不可能有连续的5个坏点出现，则8个公共点中必然有2个非坏点，则w*（f）≥9－4-6×（2/3）-3×（1/3）≥0。

d（f）＝10，由于f最多可与5个三角形相关，但由于G无四元组，所以不可能有连续的5个坏点出现，则10个公共点中必然有2个非坏点，则w*（f）≥10－4-8×（2/3）-2×（1/3）≥0。

d（f）＝11，由于f最多可与5个三角形相关，最多拥有10个公共点，则剩下的一个点最多从面收获1/3，则w*（f）≥11－4-10×（2/3）-1/3≥0。

d（f）≥12，最多f的每个点都从f面收获2/3，则w*（f）≥d（f）-4－d（f）×（2/3）≥0。

根据前述三个引理，新权重之和大于零，与欧拉公式矛盾，因此，极小平面图G不存在。故有：

定理2设G∈Γ，则G的每一个4-圈和长为6至11的圈的3-正常着色φ都可扩充到G。

3 定理1的证明

∀G∈Γ，如果G中不含4-圈、6-圈和7-圈，则图G为不含4-7圈的平面图，由文献[1]G是3-可着色的。若G有4-圈、6-圈或7-圈，由定理2，则G的每一个4-圈、6至11-圈的3-正常着色φ都可扩充到G，G是3-可着色的。从而定理1得证。

[1]Borodin O V，Glebov A N，Raspaud A，et al.Planar graphs without cycles of length from 4 to 7 are 3-colorable[J].Combin Theroy Ser B，2005，93：303-311.

[2]Bondy J A，Murty U S R.Graph Theory with Applications[M].New York：Macmillan Press Ltd，1976.

[3]赵春红，董伟.平面图3可着色的充分条件[J].南京师范大学学报：自然科学版，2011，34（3）：13-18.

[4]赵春红，蔡宇泽.一类不含5-圈平面图结构的几个结论[J].沙洲职业工学院学报，2013，16（2）：30-33.

[5]Lu Xiaoxu，Xu Baogang.A theorem on 3-colorable plane graphs[J].南京师范大学学报：自然科学版，2006，29（3）：5-8.

A sufficient condition for 3-colorable plane graphs

ZHAO Chunhong
（Department of Architectural Engineering，Shazhou Professional Institute of Technology，Zhangjiagang 215600，China）

In order to study the 3 coloring problem of plane graphs,this paper uses the method of transferring the right to prove a sufficient condition for 3-colorable plane graphs,i.e.every plane graph without 5-cycles of which each 4,6 or 7-cycles is not adjacent to cycles of length less than 8 is 3-colorable.

plane graph；cycle；coloring

O157.6MR（2000）Subject Classification：05C10

A

1672-0687（2015）01-0020-04

责任编辑：谢金春

2014-04-09

国家自然科学基金资助项目（10926126）

赵春红（1976-），女，重庆人，讲师，硕士，研究方向：图论与组合优化。