ON EQUITABLE COLORING OF COMPLETE $r$-PARTITE GRAPHS
Kittikorn Nakprasit, W. Saigrasun · International Journal of Pure and Apllied Mathematics · 2011
Let χ=(G) denote the equitable chromatic number of a graph G and let K(m1,m2, . . . ,mr) denote a complete r-partite graph with m1 ≤ m2 ≤ . . . ≤ mr. Note that χ=(K(m1,m2, . . . ,mr)) ≥ 1 + ∑r i=2⌈mi/(m1 + 1)⌉. 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(m1,m2, . . . ,mr) with complexity O(rm1). Moreover for a complete bipartite graph K(m1,m2) and a given integer m1, we find the minimum integer C such that for every integer m2 ≥ C implies χ=(K(m1,m2)) = 1 + ⌈m2/(m1 + 1)⌉. For a complete r-partite graph K(m1,m2, . . . ,mr) with m1 ≤ m2 ≤ . . . ≤ mr; r ≥ 3 and a given integer m1, we find the minimum integer C∗ such that for every integer m2 ≥ C ∗ implies χ=(K(m1,m2, . . . ,mr)) = 1 + ∑r i=2⌈mi/(m1 + 1)⌉. AMS Subject Classification: 05C15, 05C35