Equitable Total Coloring of Kn(o)del Graph WΔ,n
A k-total coloring of a graph G is a map σ: V (G)∪E(G)→”1,2,...,k” such that no two adjacent or incident elements of V(G)∪E(G) receive the same color.The total chromatic number is the smallest one out of all the k such that G has a k-total coloring.A k-total coloring is equitable if ‖σ-1(i)|-|σ-1(j)‖≤1 for each pair of distinct colors i and j (1≤i,j≤k).The smallest one out of all the k for which G has an equitable total k-coloring is named equitable total chromatic number.It is known that the problem of determining the total chromatic number is NP-hard,and it remains NP-hard for Δ-regular bipartite graphs with Δ≥3.In this paper,we show that the equitable total chromatic number of Kn(o)del Graph WΔ,n is Δ+1 while Δ=3,4,5 for all even n≥2Δ except W3,10.The result determines the total chromatic numbers of Kn(o)del graphs W3,n,W4,n,and W5,n,also is relevant as an evidence that every regular graph with Δ≤5 is such that the total chromatic number is equal to the equitable total chromatic number.
Total coloring Equitable total coloring Total chromatic number Equitable total chromatic number Kn(o)del graph
Chunling Tong Aijun Dong Shouqiang Wang Yuansheng Yang
College of Information Science and Electricity Engineering,Shandong Jiaotong University,Jinan 250023 College of Science,Shandong Jiaotong University,Jinan 250023,China College of Computer Science,Dalian University of Technology,Dalian 116024,China
国内会议
济南
英文
1-10
2014-10-16（万方平台首次上网日期，不代表论文的发表时间）