具体平面图顶点着色色数的确定

雷  明

（二○○八年六月三日）

    任意图顶点着色色数的界是ω≤γ≤1.5ω，且当ω＝4时，γ≡4。式中γ代表色数，ω代表图的密度。

（1）当图的密度ω＝1时，代入上式得γ＝1；

（2）当图的密度ω＝2时，代入上式得γ＝2 或3。当图中含有奇圈时γ＝3，这是因为奇圈中对于任何一个K₂团，均存在着一条不可同化道路，其上总有一个顶点是同化不到那个K₂团中去的；ω＝2的其他情况下γ都等于2。

（3）当图的密度ω＝3时，代入上式得γ＝3 或4。当图中含有奇轮时γ＝4，这是因为奇轮中对于任何一个K₃团，均存在着一条不可同化道路，其上总有一个顶点是同化不到那个K₃团中去的；ω＝3的其他情况下γ都等于3。

（4）当图的密度ω＝4时，上式的结果是γ≡4。

对于一个具体的平面图，其顶点着色的色数是多少，就可以在着色之前用这种方法确定下来的。可见对于任何一个平面图，其色数都是小于等于4的。

雷  明   

二○○八年六月三日于金堆城

注：本文于二○○八年十一月七日在《数学中国》网站上发表。