IJPAM: Volume 71, No. 2 (2011)

ON EQUITABLE COLORING OF
COMPLETE $r$-PARTITE GRAPHS

Keaitsuda Nakprasit$^1$, Withit Saigrasun$^2$
$^{1,2}$Applied Mathematics Research Group
Faculty of Science
Khon Kaen University
40002, THAILAND


Abstract. Let $\chi _{=}(G)$ denote the equitable chromatic number of a graph $G$ and let $K(m_1, m_2, \ldots, m_r)$ denote a complete $r$-partite graph with $m_1\leq m_2\leq \ldots \leq m_r.$ Note that $\chi_{=}(K(m_1, m_2, \ldots, m_r)) \geq 1+ \sum_{i=2}^{r} \lceil m_i/(m_1+1)\rceil. $ In this paper, we investigate the neccessary 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, \ldots, 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, \ldots, m_r)$ with $m_1\leq m_2\leq \ldots \leq m_r;\;r\geq 3$ 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,\ldots ,m_r))= 1+ \sum_{i=2}^{r} \lceil m_i/(m_1+1)\rceil .$

Received: May 4, 2011

AMS Subject Classification: 05C15, 05C35

Key Words and Phrases: equitable coloring, complete $r$-partite graph, algorithm

Download paper from here.


Source: International Journal of Pure and Applied Mathematics
ISSN printed version: 1311-8080
ISSN on-line version: 1314-3395
Year: 2011
Volume: 71
Issue: 2