Equitable Δ-coloring of graphs

AbstractConsider 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 K2n+1,2n+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