Title
Total-colorings of complete multipartite graphs using amalgamations.
Abstract
This paper makes progress towards settling the long-standing conjecture that the total chromatic number χ″ of the complete p-partite graph K=K(r1,…,rp) is Δ(K)+1 if and only if K≠Kr,r and if K has an even number of vertices then Σv∈V(K)(Δ(K)−dK(v)) is at least the number of parts of odd size. Graphs of even order that are fairly close to being regular are the ones for which χ″(K) remains in doubt. In this paper we show that K is of Type 1 if |V(K)| is even and r2<r3 (with parts arranged in non-decreasing order of size), thereby improving on the result of Dong and Yap published in 2000. Furthermore, it is shown using this result together with the novel approach of graph amalgamations that all complete multipartite graphs of the form K(r,r,…,r,r+1) are of Type 1.
Year
DOI
Venue
2016
10.1016/j.disc.2015.12.032
Discrete Mathematics
Keywords
Field
DocType
Total coloring,Graph amalgamation,Multipartite graph
Discrete mathematics,Graph,Combinatorics,Total coloring,Multipartite,Vertex (geometry),Multipartite graph,Parity (mathematics),Conjecture,Mathematics
Journal
Volume
Issue
ISSN
339
5
0012-365X
Citations 
PageRank 
References 
0
0.34
0
Authors
3
Name
Order
Citations
PageRank
Aseem Dalal131.53
B. S. Panda29921.18
C. A. Rodger318935.61