[原创]图的任何着色都可归结为给其图值函数的着色

雷明85639720

[watermark]
图的任何着色都可
归结为给其图值函数的着色
雷  明
（二○○八年八月四日）
所谓图值函数就是把图的各元素（顶点、边和面）分别作为新的顶点，而把各元素之间的相伴关系（相邻和关联）作新的边，得到的新图就是原图的图值函数。这样线图和全图等就都是原图的图值函数。所谓的线着色就是对线图的顶点着色，全着色就是对全图的顶点着色等。平面图的对偶图也是原图的图值函数，所以平面图的面着色就是对其对偶图的顶点着色。当然图的顶点着色也就是对图本身原有的顶点进行着色。
在我的《图论法证明四色猜测》一文中已经得到任意图顶点着色的色数γ的界是既不小于其密度ω又不大于其密度ω的一倍半，即ω≤γ≤1.5ω。所以图的任何着色的色数的界，只要把其图值函数的密度代入其中即可得到。
1、由于平面图的对偶图仍是平面图，所以平面图的对偶图的密度仍是ω≤4的。又由于《图论法证明四色猜测》一文中得到任意平面图的顶点着色数是γ≤4，所以平面图的面着色数也是γ面≤4；
2、线图的密度是原图的最大度Δ，所以图的线着色数的界是Δ≤γ线≤＜1.5Δ＞。1964年由V•G•Vizing给出的线色数的界Δ≤γ线图≤Δ＋1，只有下界是正确的，其上界只有在Δ＝2和3时，才是正确的。同样也有平面图面图色数的界是Δ面度≤γ面图≤＜1.5Δ面度＞。         
3、全图的密度是原图的最大度加1即Δ＋1，所以图的全着色数的界是Δ＋1≤γ全≤＜1.5（Δ＋1）＞。1965年由Behzad提出的全色数猜想γ全图≤Δ＋2，只有上界而没有下界，而且上界也只有在Δ＝1和2时，才是正确的。同样也有平面图顶面全图色数的界是Δ面＋1≤γ顶面全图≤＜1.5（Δ面＋1）＞。     
4、图值函数顶点着色色数的界：
图函数的色数的界都只与原图的最大度和度有关，与其顶点多少无关，即图值函数的密度为ω图值函数＝f（Δ原图或d原图）代入任意图顶点着色数的界中得任意图任何着色即图值函数着色时色数的界是：
f（Δ原图）≤γ图值函数≤＜1.5 f（Δ原图）＞

雷  明
                  二○○八年八月四日于金堆城

wangyangke

（笑话）继鲁思顺——定理：鲁思顺是个二百五！——之后，陕西雷明举重若轻，轻松证明哥德巴赫猜想