Equitable coloring of Kronecker products of complete multipartite graphs and complete graphs

Abstract

A proper vertex coloring of a graph is equitable if the sizes of color classes differ by at most 1. The equitable chromatic number of a graph $G$, denoted by ${\chi }_{=}(G)$, is the minimum $k$ such that $G$ is equitably $k$-colorable. The equitable chromatic threshold of a graph $G$, denoted by ${\chi }_{=}^{\ast }(G)$, is the minimum $t$ such that $G$ is equitably $k$-colorable for $k\ge t$. In this paper, we give the exact values of ${\chi }_{=}(K_{m_1,...,m_r}\times K_n)$ and ${\chi }_{=}^{\ast }(K_{m_1,...,m_r}\times K_n)$ for ${\sum }_{i=1}^r{m}_i\le n$.

11 pages. arXiv admin note: substantial text overlap with arXiv:1208.0918, arXiv:1207.3578

References in corpus (1)

• Equitable chromatic threshold of complete multipartite graphs