On equitable coloring of bipartite graphs

AbstractIf the vertices of a graph G are partitioned into k classes V1, V2, …, Vk such that each Vi is an independent set and ‖Vi| − |Vj‖ ⩽ 1 for all i ≠ j, then G is said to be equitably colored with k colors. The smallest integer n for which G can be equitably colored with n colors is called the equitable chromatic number χe(G) of G. The Equitable Coloring Conjecture asserts that χe(G) ⩽ Δ(G) for all connected graphs G except the complete graphs and the odd cycles. We show that this conjecture is true for any connected bipartite graph G(X, Y). Furthermore, if |X| = m ⩾ n = |Y| and the number of edges is less than ⌊m/(n + 1)⌋(m − n) + 2m, then we can establish an improved bound χe (G) ⩽ ⌈m/(n + 1)⌉ + 1