Total-colorings of complete multipartite graphs using amalgamations

详细信息    查看全文

• 作者：Aseem Dalal^a ; ^{aseem.dalal@gmail.com" class="auth_mail" title="E-mail the corresponding author} ; B.S. Panda^a ; ^{bspanda@maths.iitd.ac.in" class="auth_mail" title="E-mail the corresponding author} ; C.A. Rodger^b ; ^{rodgec1@auburn.edu" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Total coloring ; Graph amalgamation ; Multipartite graph
• 刊名：Discrete Mathematics
• 出版年：2016
• 出版时间：6 May 2016
• 年：2016
• 卷：339
• 期：5
• 页码：1587-1592
• 全文大小：363 K

文摘

This paper makes progress towards settling the long-standing conjecture that the total chromatic number χ^″${\chi }^{″}$ of the complete p$p$-partite graph ac6bee5" title="Click to view the MathML source">K=K(r₁,…,r_p)$K=K(r_1,\dots ,r_p)$ is Δ(K)+1$\Delta \left(K\right)+1$ if and only if K≠K_r,r$K\ne K_{r,r}$ and if K$K$ has an even number of vertices then Σ_v∈V(K)(Δ(K)−d_K(v))${\Sigma }_{v\in V\left(K\right)}(\Delta \left(K\right)-d_K\left(v\right))$ 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)${\chi }^{″}\left(K\right)$ remains in doubt. In this paper we show that K$K$ is of Type 1 if ac29" title="Click to view the MathML source">|V(K)|$\left|V\left(K\right)\right|$ is even and r₂<r₃$r_2<r_3$ (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)$K(r,r,\dots ,r,r+1)$ are of Type 1.