Equitable ΔΔ-coloring of graphs

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