关于图全染色的几个新结果.pdfVIP

关于图全染色的几个新结果 杨建国，许三星 北京科技大学应用学院，北京（100083 ） E-mail ：shuangjiang860112@ 摘 要：本文研究了图正常边染色和图全染色的一定关系,利用图正常边染色的相关结论,得 到了图全染色的几个新结果,提供了深入研究图全染色的一种可行方法. 关键词：正常边染色，正常全染色，可行方法 中图法分类：O157 文献标识码：A 1. 引言 图G 的全 k 染色是指用 k 种颜色对G 的顶点和边同时进行染色,使得相邻或相关联的 两个元素不染同一种颜色. 图G 的全染色数T (G) 是指G 的全 k 染色的最小整数 k. 1965 年,Behzad 和Vizing 各自独立地猜测:任何简单图G 是全∆+ 2 可染的. 用T (G) 记图G 的全色数,用 (G) 记图G 的边色数. χ Vizing 猜想[1] 任何简单图G 都有(∆+2)全染色. 目前人们不能全面地解决此猜想,而只能研究一些特殊图尤其是具有某些约束条件的全染色 及全色数[2,3,4 ] . 2. 正文 定理1：任何简单图G 都有(∆+ 2)全染色,若有∆(G) V(G) −1成立. 证明：对任意由上述条件的简单图G ,记其全色数为T (G) ,不妨设G 的定点个数为n ,则 有T (G) ≤T (K n ) ,因此我们只需证明K n 有(∆+2) 全染色即可. 在n 阶完全图K 中,从每一个顶点引出一条边,令此n 条边相交于一个新的顶点,记为 n vn+1 ,记新增顶点后的图为G ,则G 是最大度为n 的K n+1 阶完全图,而由 Vizing 定理 知, K 的边色数 (K ) ≤(n +1) ,若以K 新增的这n 条边的颜色来代替K 中相应 n+1 χ n+1 n+1 n 的这n 个顶点的颜色, 则可将K n 中任意相邻或者相关联的元素区分开, 故有关系 T (G) ≤T (K n ) ≤χ(Kn+1) ≤(n +1) 成立,而又有∆(G) ∆(K n ) n −1, ∆(G) +2 = n +1, 由上面的分析知：简单图G 有(∆+ 2)全染色. 推论1：任何奇数阶简单图G 都有(∆+1)全染色,若有∆(G)