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

与G 中的每个顶点连接,则有 ) ' G GT χ≤ ( ( http://www.paper.edu.cn ' ) 证明：由定理的证明,很容易验证此结论成立. 通过推论 2,我们就可以通过现有的一些边色数的成果来研究图的全色数. 推论 3：在 ∆ GVG ( = ( ) 1) − 0vG + 为第一类图,则有 得简单图G 中,若 +∆=GT ( ) 1 ) +∆≤GT 证明：由推论 2 知 故有 定理 2: 完全图 nK 的全色数等于 1+nK 的边色数. +∆=GT 成立. 1 1 ( ) ( 成立,而又由 Vizing 定理知 +∆≥GT ) ( 1 ' 1 , t ( χ =+ ) nK λ 证明：设 n =) 成立 KT ( 先证 λ≤t 若用λ种颜色可对 1+nK 进行正常边染色,在任一种着色方案中,任意去掉一个顶点,对 应去掉的那 n -1 条边的颜色相应的赋给相应的那 n -1 个顶点,则这种着色方案同样可以区分 开 nK 中任意两个相邻的元素,故有 λ≤t 同理采用相同的转换方法可以证明 故有结论 λ=t 成立. t≤λ 成立. 推论 4： +∆=nKT ( ) 2 成立. +∆=+nKT 2 ( , ' K nχ n 2 ) =+ 1 ) ( 1 2 1 ' K nχ 2 2 2 , ( ) ) 1 1 − + 先看引理 ]5[ = n 2 证明：由上述定理结合以上引理,可以很容易得得到结论 +∆=nKT ( 上面研究的是简单图G 的情况,对于有重边的图G ,平行的有下面结论成立. 对应简单图G 的 Vizing 定理,Vizing 和 Gupta 证明了如下结论 引理：对于有重边的无环图G ,有 +∆=+nKT ( 成立. 成立. G ( µ ∆≤ G ( + 2 1 ) ) ) ) , 1 2 (' χ G ) (Gµ 是G 的最大边重数. ) G ) ( + µ 成立,则有 G 1) ( + µ (Gµ 是最大边重数. 其中, 记G 为一有重边的无环图, GE G 定理 3：若图G 有 ) ( ( ∆ = GT 1 ) ( ≤+∆ +∆≤ 证明：对于图 G ,不妨设 G 的顶点个数为 n ,从 G 的每一个顶点引出一条边让其相交于 vn 1+ , 则 记 'G = G + vn 1+ , 由 上 述 引 理 知 χ G ( ) ∆= 种颜色对 'G 进行边染色,若用新增边的颜色来代替 G 中对应 n 个 2) − 成立 G µ G ( ( G µ G ( ( µ = 1) ++ G ( µ G ( µ 1) + 1) + ∆= ∆≤ , 则 G ( G ( G ( G ( ∆ ∆ + + , ) ) ) ) ) ) ) , ' ' ' ' ' ' 故可用 顶点的颜色,则可对G 进行完美全染色,故有 GT ) 显然成立,故定理结论得证. ( 左边 GT≤+∆ 1 ( ) +∆≤ G ( µ 1) + 成立 - 2 - 

http://www.paper.edu.cn 猜想：对于有重边的图G , ) ≤+∆ GT (Gµ 是G 的最大边重数.有 +∆≤ ) G ( µ 成立 1) + 1 ( 3. 结论 本文通过构造得到了图正常边染色和图全染色的一定联系,可充分利用图正常边染色的 结果来研究图全染色,更大意义不是在于文章中的几个定理,而是提供了一种研究图全染色的 几种方法,很容易的看出,沿着这个思路,还可以对图全染色做更深入的研究. 参考文献 [1] Vizing V G. On an estimate of the chromatic class of a p - graph(in Russian) [J ] .Metody Diskret Analiz ,1964 ,3 :25-30 [2] 耿建艳 侯建锋 最大度为 6 且不含 5-圈或 6-圈的平面图 8-全染色[J]山东大学学报 2006(10):55-58. [3]孙向勇.关于 3-全不重点的平面图全染色的一个结论[J].山东建筑大学学报 2006:21(4):374-376. [4]孙向勇 特殊平面图的全染色[J].山东师范大学学报.2007(3):10-12. [5]Fred Buckley,A Friendly Introduction to Graph Theory[M] 清华大学出版社,第一版. Several New Results on the Total Coloring of Graph Application Schoool of University of Science And Technology Beijing，Beijing (100083) Yang Jianguo，Xu Sanxing Abstract This article has studied some relation between the normal side-coloring and the total coloring of graph using some relative results about the normal side-coloring,which has obtained several new results and offered one feasible method in researching the total coloring of graph. Keywords：normal side-coloring，total coloring，feasible method - 3 -