关于圈的着色问题

雷明85639720

关于圈的着色问题
雷  明
（二○二一年十一月十四日）

图论中有关圈的定义有多种。一种是从图中的任一顶点开始，沿着不重复的边和不重复的顶点走下去，最后又回到原出发顶点。把这条闭合途径称为圈。哈密顿回路就是这样的圈。还有一种圈是只讲沿着不重复的边，而不说顶点重复不重复，又回到原出发顶点时的闭合途径。前者是普通圈，后者则是更复杂一些的圈（如尤拉圈）。我们这里只研究普通圈的着色问题。
圈也是一个平面图，如果四色猜测是正确的（因为目前四色猜测还没有被证明是否是正确的，所以也只能这样进行假设），那么圈也一定是可4—着色的。圈在着色时，所用颜色一定是不会超过四种的。
一个圈既可以是一个单独的图，也可以是图中的一个分子图。作为一个单独的图来说，图中的边数与顶点数一定是相等的，但作为一个图中的分子图来说，圈的两侧都可能还存别的顶点和边。当圈的两侧再无别的顶点时，则与单独的圈相同。着色时也一定是偶圈是2—色的，奇圈是3—色的；当圈的一侧还有别的顶点或边时，这时的圈的着色就不是那么简单的偶圈是2—色的和奇圈是3—色的问题了。
极大平面图中，所有的面都是三边形面，各面也都是一个奇圈（边数最少的圈），也都是3—色的。任何相邻的两个面也都是一个4—圈（偶圈），这个4—圈中一定有一对对角顶点是有对角线相邻的，而着色时相邻的顶点又不能着同一颜色，所以4—圈作为一个单独的图时是2—色的，而现在作为图中的一个分子图时的4—圈，就不能只是2—色的了，必须要三种颜色或者四种颜色才能完成正确的着色。如四面体中的所有4—圈，都是占用了4—种颜色的。
请朋友们看一看，在任一个已正确4—着色的极大平面图中，是不是这样的呢？虽然图中可能仍然还有个别的偶圈（包括4—圈）是只用了两种颜色的（如一个偶轮，轮沿顶点可能只占用了两种颜色），但一定存在着有些偶圈一定是着了三种颜色的，或者甚至是用了四种颜色的。4—轮（偶轮）的轮沿顶点（一个4—圈）虽然只占用了两种颜色，但其中的任何一个4—圈却都是3—色或4—色的。
由于这种情况的存在，所以说，圈作为一个单独的图时，偶圈一定是2—色的，奇圈也一定是3—色的；但圈作为某图中的一个分子图时，这一规律也就不存在了。只要在不违反四色猜测原则的情况下，该用几种颜色就用几种颜色，也都是合理的。因为整个图中所用的颜色数是没有大于4种的。
虽然单独的偶轮是2—色的，单独的奇轮是3—色的，但分别着上3色或4色的时，也不算错。因为还是符合四色猜测要求的，用色是没有超过4的；更是符合着色要求的，用色再多，也是达到了相邻顶点不用同一颜色的目的。所以，着色与四色猜测是不同的两回事，着色要求的是相邻的顶点不用同一种颜色以相互区别，而四色猜测要求的则是在满足相邻顶点不用同一种颜色的前提下，所用颜色种数还要是最少的，即色数是小于等于4的。
现在市面上销售的地图，无论是以国家级区划为染色单元的，还是以省级区划为染色单元的，甚至更低一级的以区县级区划为染色单元的地图，一般都至少用了六种颜色，有的可能还要更多。虽然这不符合四色猜测的原则，所用的颜色数不是最少的，但却也算是对地图的一个着色，也满足了相邻的区划不用同一种颜色的要求和目的。你不能笼统的说这样的着色就是错误的。只能说对于要求用色最少的四色猜测来说，着色是错误的；而对于区分图中的相邻区划（或顶点）来说，其着色则不能算错。
这就是我对圈的着色的看法。请网友们提出不同的意见。

雷  明
二○二一年十一月十四日于长安

朱明君

，，，，，，，