Equitable Δ-coloring of graphs

Publication year: 2011
Source: Discrete Mathematics, In Press, Corrected Proof, Available online 14 June 2011

Bor-Liang, Chen , Chih-Hung, Yen

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 asserts that a connected graph G with Δ(G)≥χ(G) is equitably Δ(G)-colorable…