Equitable Chromatic Number of Complete Multipartite Graphs
Dorothee Blum, Denise Torrey, Richard H. Hammack · Missouri Journal of Mathematical Sciences · 2003
The equitable chromatic number of a graph is the smallest integer $n$ for which the graph's vertex set can be partitioned into $n$ independent sets, each pair of which differs in size by at most 1. We develop a formula and a linear-time algorithm which compute the equitable chromatic number of an arbitrary complete multipartite graph. These results yield tractable solutions of certain scheduling problems.