【作者】 马刚；

【导师】 张和平；

【作者基本信息】 兰州大学 ， 应用数学， 2007， 硕士

【摘要】 对图G的k-全染色法f，如果（?）i，j∈{1，2，…，k)，有||T_i|-|T_j||≤1，则称f为G的一个k-均匀全染色法，简记作G的k-ETC法。而称为G的均匀全色数。其中T_i=V_i∪E_i，（?）x∈T_i，f（x）=i。本文研究了简单图的均匀全染色，给出了χ_et（G）=Δ（G）+1的一个充分条件和图在一定条件下均匀全色数的一个上界，结果如下：定理1对于简单图G，若Δ（G）=|V（G）|-1，且|V（G）|≡1（mod 2），则定理2对于简单图G，若Δ（G）≤|V（G）|-2，则χ_et（G）≤|V（G）|。由以上定理可推出一系列满足特殊条件的联图或多重联图的均匀全色数（见第三章）。在第四章中我们得到了P_m∨S_n、P_m∨F_n、P_m∨W_n、C_m∨S_n、C_m∨F_n和C_m∨W_n在m，n不同取值情况下的均匀全色数（见定理4至定理9）。在第五章中我们给出了星、扇和轮的Double图的均匀全色数（见定理10至定理12）。最后在所研究的基础上给出了关于图的均匀全染色问题的两个新的猜想：猜想若图G仅有一个最大度点，则χ_et（G）=Δ（G）+1。猜想若图G的最大度点互不相邻，则χ_et（G）=Δ（G）+1。更多还原

【Abstract】 A total-coloring is said to be equitable if‖T_i|－|T_j‖≤1, where|T_i| is the elements （vertices and edges） number of the color ith. The minimum number of colors required for an equitable total-coloring of a simple graph G is denoted by x_et（G）.We study equitable total-coloring of simple graphs and obtain one sufficient condition for x_et（G）=△（G）＋1 and an upper bound of x_et（G） under some conditions:Theorem 1 Let G be a simple graph. If△（G）=|V（G）|－1 and|V（G）|≡1（mod2）, then x_et（G）=△（G）＋1.Theorem 2 Let G be a simple graph. If△（G）≤|V（G）|－2, thenx_et（G）≤|V（G）|.According to these theorems, we obtain the equitable total chromatic number of （multi） Join-graphs satisfying some conditions （to see Chapter 3）. In Chapter 4 we obtain the equitable total chromatic numbers of P_m∨S_n, P_m∨F_n,P_m∨W_n,C_m∨S_n,C_m∨F_n and C_m∨W_n for all m,n（to see from Theorem 4 to Theorem 9）. In Chapter 5 we derive the equitable total chromatic numbers of Double graphs of Star, Fan and Wheel （to see from Theorem 10 to Theorem 12）. Finally, we propose two conjectures on Equitable Total-Coloring.Conjecture 1 Let G be a simple graph. If G only has a vertex with maximum degree, then x_et（G）=△（G）＋1.Conjecture 2 Let G be a simple graph. If G’s vertexes with maximum degree are not adjacent, then x_et（G）=△（G）＋1.更多还原