06018736

j

06018736 Nakprasit, Keaitsuda Saigrasun, Withit On equitable coloring of complete $r$-partite graphs. Int. J. Pure Appl. Math. 71, No. 2, 229-239 (2011). 2011 Academic Publications, Sofia EN equitable coloring complete $r$-partite graph algorithm

http://www.ijpam.eu/contents/2011-71-2/5/index.html

Summary: Let $\chi _{=}(G)$ denote the equitable chromatic number of a graph $G$ and let $K(m_1, m_2, \dots, m_r)$ denote a complete $r$-partite graph with $m_1\leq m_2\leq \dots \leq m_r$. Note that $\chi_{=}(K(m_1, m_2, \dots, m_r)) \geq 1+ \sum_{i=2}^{r} \lceil m_i/(m_1+1)\rceil$. In this paper, we investigate the necessary conditions on the number of vertices such that this bound is attained. By using those conditions, we obtain the algorithm to find the equitable chromatic number of a complete $r$-partite graph $K(m_1, m_2, \dots, m_r)$ with complexity $O(rm_1)$. Moreover for a complete bipartite graph $K(m_1, m_2)$ and a given integer $m_1$, we find the minimum integer $C$ such that for every integer $m_2 \geq C$ implies $\chi_{=}(K(m_1, m_2))= 1+\lceil m_2/(m_1+1)\rceil$. For a complete $r$-partite graph $K(m_1, m_2, \dots, m_r)$ with $m_1 \leq m_2 \leq \dots \leq m_r$;$\, r \geq 3$ and a given integer $m_2 \geq C^*$ implies $\chi_{=}(K(m_1, m_2, \dots, m_r))=1+\sum^{r}_{i=2} \lceil m_i/(m_1+1)\rceil$.