如何给无割边的3—正则图平面图进行3—边着色和4—面着色

雷明85639720

如何给无割边的3—正则图平面图进行3—边着色和4—面着色
雷  明
（二○一七年八月二十六日）

我们在给无割边的3—正则的平面图在进行3—边着色时，已经发现并总结出了如下的规律：含奇数边面的图在可3—边着色时，一定出现3—色圈的面，在可4—面着色时，面色数一定是4；而不含奇数边面的图在可3—边着色时，则可以不出现3—色圈的面，所有面均是2—色圈，在可4—面着色时，面色数一定是3，否则面色数则是4。
根据这样的规律，任给一个无割边的3—正则的平面图，首先要看图中含不含奇数边面：如果含有奇数边面，其面着色的色数一定是4；如果不含奇数边面时，则其面着色的色数一定是3。
以上只是判断无割边的3—正则平面图面着色色数的值是多少，而对其可3—边着色时，具体的则应是：
1、图中若含有奇数边面时，先要对其进行一次哈密顿遍历，看走完图中所有的顶点时，还能不能回到原来的出发点：若能，这个图就是可哈密顿的；否则就是不可哈密顿的。
①　若图是不可哈密顿的时，图进行可3—边着色后，各种边2—色圈一定至少有两个，可以先在图中着一个较小的1—2—1边2—色圈，然后再在所剩的边中，用1和2两种颜色再着边2—色圈。能遍历所剩顶点且又能回到原出发点时，把再剩下来的边全部着上第三种颜色3，这个图的可3—边着色就完成了；虽能遍历所剩顶点，但回不到原出发点时，就再重复以上的操作即可，最后总可以使所有的顶点都在1—2—1边2—色圈上。面色数一定是4。
②　若图是可哈密顿时的时，1—2—1边2—色圈一定是一个遍历，且能回到出发点，把剩下的边全着上第三种颜色3即可。这个图的可3—边着色也就完成了。面色数也一定是4。
2、若图中所有面全是偶数边面时，每个面边着色时两种颜色就够用了，所以每个面一定都可以着成2—色圈。但这里一定要防止把偶数边面着成3—色圈的情况。把偶数边面着成3色圈的这种情况出现后，虽然图仍是可以3—边着色的，但最后的面着色色数就不是3而是4了，这是不符合要求的，所以一定要防止这一现象的出现。

无割边的3—正则平面图的可3—边着色完成后，就可以用颜色叠加法进行可4—面着色了。这种方法的操作是这样的：所有的1—2—1边2—色圈，把图分成了若干个部分，给各部分相间的着以不同的两种颜色A和B；所有1—3—1边2—色圈，也把图分成了若干个部分，给各部分相间的着以不同的两种颜色C和D；然后再把两次分别用A、B和C、D两种颜色相间着色所得到的二色图“叠加”起来，便会产生不多于AC，AD，BC和BD四种的新颜色，分别着在了图中的各个面上，有共同边界的两个相邻面没有着相同颜色的情况。该图的可4—面着色完成。

以上的操作，把各种情况下的无割边的3—正则的平面图都考虑到了。它他都是可3—边着色的，也都是可4—面着色的。


雷  明
二○一七年八月二十六日于长安

注：此文已于二○一七年八月二十六日在《中国博士网》上发表过，网址是：

雷明85639720

，，，，

雷明85639720

，，，，