论图的色数、全色数猜想及四色定理

           论图的色数、全色数猜想及四色定理
摘要   在假设文中提出的“胡氏猜想”成立的前提下，本文得到了以下结果：
一、找到了一种方法，可以确定简单无向图的顶点色数（对绝大多数类型的图能准确判断顶点色数，只对一种类型的图判断顶点色数有误差但误差不大于1）。
二、给出了全色数猜想的一个证明。
三、给出了四色定理的一个证明，同时给出了上文中不能准确判断顶点色数图的另一种判定方法，可准确判定顶点色数。


定义    设G(V,E)是简单无向连通图，顶点v∈G，记G中到v的距离不大于2的顶点集合为Vv（含v本身），Vv在G中的导出子图记为Gv(Vv,Ev)，Gv的顶点色数记为χ（Gv），
max[χ（Gv）,v∈G]是G中所有顶点的χ（Gv）的最大值，G的顶点色数记为χ（G）。

定义（对点）   设max[χ（Gv）,v∈G]=r≥2，若G(V,E)存在顶点v1、v2及子图G1满足：
(1)v1、v2在G中的距离为2且都不属于G1。
(2)G1的每个顶点都与v1、v2相邻（关联）。
(3)χ（G1）=r-1，且G1去掉任意顶点或任意边之后所得图的顶点色数小于（r-1）。
则称v2是v1的1级对点（v1是v2的1级对点）。
若v3不是v1的1，......，（i-1）级对点，但v3存在1级对点是v1的（i-1）级对点，则称v3是v1的i级对点。
v1的任意级对点都称为v1的对点。

定义（两种情形）  设G(V,E)是简单无向连通图，max[χ（Gv）,v∈G]=r≥2，称G存在情形（1），若G满足：G的某个顶点有2个对点相邻。[情形（1）可以称为“G存在相邻对点”]
称G存在情形（2），若G满足：
（i）v1、v2∈G，v1不是v2的对点（自然v2也不是v1的对点）。
（ii）χ（Gv2）=r，且χ（Gv2）存在顶点色数为r的子图G'v2,使得G'v2的每个顶点都与v1的对点相邻。

定理1   设简单无向连通图G(V,E)满足：
（1）max[χ（Gv）,v∈G]=r≥2。
（2）G不存在情形（1）及情形（2）。
则存在G’(V’,E’)，满足：
（i）G是G’的子图， χ（G）=χ（G'），max[χ（G'v）,v∈G']=r。
（ii）G'不存在情形（1）及情形（2）。
（iii）G'存在顶点v，使得G'中任意顶点到v的距离不大于3。

胡氏猜想：设简单无向连通图G(V,E)满足：
（1）max[χ（Gv）,v∈G]=r≥4。
（2）G不存在情形（1）及情形（2）。
（3）G存在顶点v，使得G中任意顶点到v的距离不大于3。
则 χ（G）=r。

定理2    设G(V,E)是简单无向连通图，max[χ（Gv）,v∈G]=r，则χ（G）≤r+1，等号成立当且仅当G符合以下条件之一：
（i）G存在情形（1）。
（ii）G存在情形（2）。
（iii）r=3。

定理1、定理2的意义  找到了判定简单无向图的顶点色数的方法，而且该方法是可行的：若G中任意顶点都有距离为3的点，则只需考虑每个Gv的顶点色数，计算复杂度比整体考虑G的顶点色数要低得多。

若胡氏猜想成立，则全色数猜想成立。证明过程如下。
设G(V,E)是简单无向连通图，称‍G'(V',E')是G的全色等价图，若G'满足：‍
（1）V'=V∪V1,V‍∩V1=Φ，‍V1与E形成一一映射。‍
（2）E'=E∪E1‍∪E2;E1={(va,vb)|va∈V,vb∈E,vb是va在G中的关联边},E2={(va,vb)|va∈E,vb∈E，va、vb在G中有公共顶点}。
显然，G的全色数与G'的顶点色数相等。G'不是完全图。
当G是完全图Kr，已经知道G的全色数不大于(r+2)，即G的全色等效图的顶点色数不大于（r+2），且容易知道G的全色等效图不存在对点，自然不存在情形（1）及情形（2）。

若G不是完全图，设G的顶点最大度为r，则G的顶点色数不大于r。考虑G'v。
G'v的顶点可以分为两部分：第一部分对应于Gv中到v的距离为2的顶点；第二部分是G中v、v的邻点以及它们的关联边在G'中的对应顶点。G'v的第二部分顶点的导出子图真包含于Kr的全色等价图，即其顶点色数不大于（r+2）。由于G'v的第一部分的顶点的度不大于r，则‍χ（G'v）≤（r+2）。显然G'中不存在对点，即不存在情形（1）及情形（2）。由胡氏猜想成立的前提知χ（G'）‍≤（r+2），即G的全色数不大于（r+2）。证毕。‍
--------------------
要证明四色猜想，只需证明任意极大平面图的顶点色数为4。运用数学归纳法可知，只需证明顶点的度都不小于5的极大平面图的顶点色数为4。易知顶点度最小为5的极大平面图的阶数（顶点数）不小于12。
定义（素图）：若极大平面图G的‍顶点度最小为5，G的的任意阶数大于3的真子图都不是极大平面图，则称G为素图。
证明顶点的度都不小于5的极大平面图的顶点色数为4，只需证明素图的顶点色数为4。‍
显然，素图不存在K4,若我们能证明对任意素图G，有max[χ（Gv）,v∈G]=4，则有χ（G）=4。‍
素图对应的四正则图G'存在K3，且不存在对点——即G'的任意四个顶点的导出子图边数小于5。Gv对应于G'的图是一些K3连接形成的图，容易知道后者是可以3-上色的，即max[χ（Gv）,v∈G]=4，从而四色猜想得证明。‍

           论图的色数、全色数猜想及四色定理
摘要   在假设文中提出的“胡氏猜想”成立的前提下，本文得到了以下结果：
一、找到了一种方法，可以确定简单无向图的顶点色数（对绝大多数类型的图能准确判断顶点色数，只对一种类型的图判断顶点色数有误差但误差不大于1）。
二、给出了全色数猜想的一个证明。
三、给出了四色定理的一个证明，同时给出了上文中不能准确判断顶点色数图的另一种判定方法，可准确判定顶点色数。


定义    设G(V,E)是简单无向连通图，顶点v∈G，记G中到v的距离不大于2的顶点集合为Vv（含v本身），Vv在G中的导出子图记为Gv(Vv,Ev)，Gv的顶点色数记为χ（Gv），
max[χ（Gv）,v∈G]是G中所有顶点的χ（Gv）的最大值，G的顶点色数记为χ（G）。

定义（对点）   设max[χ（Gv）,v∈G]=r≥2，若G(V,E)存在顶点v1、v2及子图G1满足：
(1)v1、v2在G中的距离为2且都不属于G1。
(2)G1的每个顶点都与v1、v2相邻（关联）。
(3)χ（G1）=r-1，且G1去掉任意顶点或任意边之后所得图的顶点色数小于（r-1）。
则称v2是v1的1级对点（v1是v2的1级对点）。
若v3不是v1的1，......，（i-1）级对点，但v3存在1级对点是v1的（i-1）级对点，则称v3是v1的i级对点。
v1的任意级对点都称为v1的对点。

定义（两种情形）  设G(V,E)是简单无向连通图，max[χ（Gv）,v∈G]=r≥2，称G存在情形（1），若G满足：G的某个顶点有2个对点相邻。[情形（1）可以称为“G存在相邻对点”]
称G存在情形（2），若G满足：
（i）v1、v2∈G，v1不是v2的对点（自然v2也不是v1的对点）。
（ii）χ（Gv2）=r，且χ（Gv2）存在顶点色数为r的子图G'v2,使得G'v2的每个顶点都与v1的对点相邻。

定理1   设简单无向连通图G(V,E)满足：
（1）max[χ（Gv）,v∈G]=r≥2。
（2）G不存在情形（1）及情形（2）。
则存在G’(V’,E’)，满足：
（i）G是G’的子图， χ（G）=χ（G'），max[χ（G'v）,v∈G']=r。
（ii）G'不存在情形（1）及情形（2）。
（iii）G'存在顶点v，使得G'中任意顶点到v的距离不大于3。

胡氏猜想：设简单无向连通图G(V,E)满足：
（1）max[χ（Gv）,v∈G]=r≥4。
（2）G不存在情形（1）及情形（2）。
（3）G存在顶点v，使得G中任意顶点到v的距离不大于3。
则 χ（G）=r。

定理2    设G(V,E)是简单无向连通图，max[χ（Gv）,v∈G]=r，则χ（G）≤r+1，等号成立当且仅当G符合以下条件之一：
（i）G存在情形（1）。
（ii）G存在情形（2）。
（iii）r=3。

定理1、定理2的意义  找到了判定简单无向图的顶点色数的方法，而且该方法是可行的：若G中任意顶点都有距离为3的点，则只需考虑每个Gv的顶点色数，计算复杂度比整体考虑G的顶点色数要低得多。

若胡氏猜想成立，则全色数猜想成立。证明过程如下。
设G(V,E)是简单无向连通图，称‍G'(V',E')是G的全色等价图，若G'满足：‍
（1）V'=V∪V1,V‍∩V1=Φ，‍V1与E形成一一映射。‍
（2）E'=E∪E1‍∪E2;E1={(va,vb)|va∈V,vb∈E,vb是va在G中的关联边},E2={(va,vb)|va∈E,vb∈E，va、vb在G中有公共顶点}。
显然，G的全色数与G'的顶点色数相等。G'不是完全图。
当G是完全图Kr，已经知道G的全色数不大于(r+2)，即G的全色等效图的顶点色数不大于（r+2），且容易知道G的全色等效图不存在对点，自然不存在情形（1）及情形（2）。

若G不是完全图，设G的顶点最大度为r，则G的顶点色数不大于r。考虑G'v。
G'v的顶点可以分为两部分：第一部分对应于Gv中到v的距离为2的顶点；第二部分是G中v、v的邻点以及它们的关联边在G'中的对应顶点。G'v的第二部分顶点的导出子图真包含于Kr的全色等价图，即其顶点色数不大于（r+2）。由于G'v的第一部分的顶点的度不大于r，则‍χ（G'v）≤（r+2）。显然G'中不存在对点，即不存在情形（1）及情形（2）。由胡氏猜想成立的前提知χ（G'）‍≤（r+2），即G的全色数不大于（r+2）。证毕。‍
--------------------
要证明四色猜想，只需证明任意极大平面图的顶点色数为4。运用数学归纳法可知，只需证明顶点的度都不小于5的极大平面图的顶点色数为4。易知顶点度最小为5的极大平面图的阶数（顶点数）不小于12。
定义（素图）：若极大平面图G的‍顶点度最小为5，G的的任意阶数大于3的真子图都不是极大平面图，则称G为素图。
证明顶点的度都不小于5的极大平面图的顶点色数为4，只需证明素图的顶点色数为4。‍
显然，素图不存在K4,若我们能证明对任意素图G，有max[χ（Gv）,v∈G]=4，则有χ（G）=4。‍
素图对应的四正则图G'存在K3，且不存在对点——即G'的任意四个顶点的导出子图边数小于5。Gv对应于G'的图是一些K3连接形成的图，容易知道后者是可以3-上色的，即max[χ（Gv）,v∈G]=4，从而四色猜想得证明。‍