回复杨老师

雷明85639720

回 复 杨 老 师
雷  明
（二○一三年六月九日）
杨老师，我感到你好象对有些地方的理解是不太对头。比如说，你可能认为图同化的结果一定是要把某一最大团外所有的顶点都同化到这个最大团中去。不是这样的。
图同化的结果可以出现有些顶点不能同化到最大团中去的情况，这是客观存在，不是谁能不能同化上去的问题。比如说，一条不可同化道路中就一定有一个顶点不可能同化到最大团中去。因此才有了“不可同化道路”一词，无论谁也不可能把这个顶点同化到最大团中去。
举一个例子，如一个奇圈，其最大团是K2，其密度就是2，对于其中每一个K2团来说，圈上的其它顶点和边构成了该K2团的一条不可同化道路，其同化的结果一定是有一个顶点同化不到那个K2团中去的，这样，奇圈的最小完全同态就是一个K3图，它的顶点数就是3，着色时一定要用3 种颜色，色数是“大于”其密度值的。
但这个“大于”是有一定的范围的，并不是任意的。我已经证明了它是不能超过图的密度之半并向下取整的值的。圈的密度是2，其半是1，1向下取整后还是1，1＋2＝3，这就是奇圈的色数。奇圈的色数一定不会比3更大，并且只要是含有奇圈的、密度是2的图的色数也一定都是3。
但同样都是密度为2的圈，偶圈同化的结果却是K2图。因为偶圈中对于其中每一个K2团来说，圈上的其它顶点和边虽构成了该K2团的一条饱和道路，但该饱和道路却是一条可同化的道路，所以偶圈同化的最终结果却是一个K2图，其色数也就成了2，与其密度相同。
密度为2的图同化时一定只会出现以上两种结果，但都是正确的。这样不同的两种结果都是密度为2的图同化时的最终结果，不一定非都要得到所有顶点都同化到某一个最大团中去的、千篇一律的模式。如果是这样，那就不需要再去进行证明了，直接就说任意图的色数都等于它的密度不就行了吗。
因为最大团本身就是一个完全图，其中的各个顶点都是互相相邻的，着色时一定得要用与其顶点数相同数目的颜色数，这就是任意图顶点图着色色数的下界；而一个图的最小完全同态的顶点数一定是大于等于图的密度的，但又不能超过图的密度的一倍半向下取整的值，这就是任意图顶点着色色数的上界。由此二者共同组成了任意图顶点着色色数的界。但这只是一个界限，并不是某个图的具体色数。
通过对构成联的不可同化道路条数的确定，就可以确定任意图最终同化结果——最小完全同态的顶点数一定不会超过的界限，这一切都不是针对某个具体图而说的，没有必要再继续探讨所有的顶点是否都可以同化到最大团中去的问题了。因为上面得到的这个上界限已是在最复杂情况下得到的，所以即就是还有些顶点不能同化到最大团中去，但同化不到最大团中去的顶点数连同最大团的顶点数一起，也不会再超过上面已确定的上界了。
证明只能针对具有代表性的、不是具体图的图，不能象对某个具体图的着色或同化那样，最后得到的是色数的具体值或最小完全同态顶点数的具体值。
杨老师，我想你是能够理解的。
雷  明
二○一三年六月九日于长安
注：该信没有发给杨老师。
注：该文已于二○一三年六月十日在《数学中国》网上发表过。