浅议切实可行切实可行四色定理证明新办法

【摘要】本文简单介绍用图论的方法证明三角形结构连通图的不可避免构形集，同时用顺序配色的方法证明三角形结构连通图的色数≤4，也就证明平面图的色数≤

4.为四色定理证明和应用找到了切实可行的新方法.

【关键词】 三角形结构连通图； 不可避免构形集； 延伸结构； 轮形结构； 顺序配色法
【中图分类号】O156
1.前 言
四色猜想是世界数学界关注的问题，给出四色定理无需借助于计算机的证明仍然是一个未获解决的数学难题.我们已知四色定理可通过证明平面连通图G的色数≤4来实现.而平面连通图的色数不大于由它增加边而导出的三角形结构连通图G （triangulated graph）的色数.因此，只需证明任意三角形结构连通图的χ（G）≤4，即解决问题.

2.两大不可避免构形集

定理1 三角形结构连通图仅有延伸和轮形两种结构方式.
证 （1）我们可以逐个增加三角形构造三角形结构子图，由欧拉公式可证明，为了增加一个三角形（面）：1）当增加一个顶点和两条边得到的是延伸结构.2）而增加一条边会产生一个新轮形结构.（2）延伸和轮形两种结构的组合结果还是这两种类型的结构.因此三角形结构连通图只有延伸结构和轮形结构两大不可避免构形集.
引理1 轮图色数≤4.
定理2 延伸结构子图色数=3.
证 如上用逐个增加三角形构造延伸结构子图，每一个新顶点都可以用与同一个三角形中另两个顶点不同的颜色，可通过数学归纳法很容易地证明延伸结构子图色数=3.

3.图的简化和扩展

任何复杂的延伸结构和轮形结构的邻接可简化归纳为3个模块和扇形模块（见下图），由它们的扩展图组合可以构成任意的三角形结构子图.

4.顺序配色法

首先，应先对图G做好一个初步的的规划图（预分配）是形成轮形间隔源于：免费论文网www.618jyw.com
延伸结构的布局，使之出现更多小的延伸结构.然后逐个对延伸结构进行分部配色，直至完成落实全部图的顶点的正常4-着色，这一方法称之为顺序配色法（见下图）.图Ⅰ、Ⅱ 表示一组一个延伸结构与轮形结构邻接的部分配色的方法：图中Ⅰ下部Y12是前面已经着的延伸结构，上面的Y12是本次需要配色的延伸结构，中间隔着4个轮形（注：为了分清轮形与延伸结构，将所有轮形的边用浅色线表示）.图中Ⅱ是一般情况下正常4-着色的结果.轮形中心顶点用白色.延伸结构的顶点用另外三色.当使用一般的方法不能对Y12正常着色，就可以采用图中Ⅲ的方法，将轮形结构重新排列，由于有足够的位置插入新轮形将子图隔离成独立的延伸
结构碎块（互相不再有颜色冲突），由于图下边顶点保持颜色不变，使前后两个子图能很好地衔接合并无颜色冲突.由于延伸结构色数=3，轮图色数≤4，结果母图G的色数也≤4.
通过以上分析证明，不管任何复杂的平面图都可以转换成三角形结构的连通图进行分析正确安排轮形结构的位置，实施正常4-着色.这也就证明了任何平面图的色数≤4.
【参考文献】
王数禾.图论 [M].北京：科学出版社，2004.
屈婉玲， 耿素云， 张立昂. 离散数学[M]. 北京： 清华大学出版社， 2005.