Equitable -coloring of graphs

Consider a graph G consisting of a vertex set V ( G ) and an edge set E ( G ) . Let Δ ( G ) and χ ( G ) denote the maximum degree and the chromatic number of G , respectively. We say that G is equitably Δ ( G ) -colorable if there exists a proper Δ ( G ) -coloring of G such that the sizes of any two color classes differ by at most one. Obviously, if G is equitably Δ ( G ) -colorable, then Δ ( G ) ≥ χ ( G ) . Conversely, even if G satisfies Δ ( G ) ≥ χ ( G ) , we cannot guarantee that G must be equitably Δ ( G ) -colorable. In 1994, the Equitable Δ -Coloring Conjecture ( E Δ CC ) asserts that a connected graph G with Δ ( G ) ≥ χ ( G ) is equitably Δ ( G ) -colorable if G is different from K 2 n + 1 , 2 n + 1 for all n ≥ 1 . In this paper, we give necessary conditions for a graph G (not necessarily connected) with Δ ( G ) ≥ χ ( G ) to be equitably Δ ( G ) -colorable and prove that those necessary conditions are also sufficient conditions when G is a bipartite graph, or G satisfies Δ ( G ) ≥ | V ( G ) | 3 + 1 , or G satisfies Δ ( G ) ≤ 3 .