Equitable Coloring of Graphs with Intermediate Maximum Degree

Original · EN

If the vertices of a graph G are colored with k colors such that no adjacent vertices receive the same color and the sizes of any two color classes differ by at most one, then G is said to be equitably k-colorable. Let |G| denote the number of vertices of G and Δ=Δ(G) the maximum degree of a vertex in G. We prove that a graph G of order at least 6 is equitably Δ-colorable if G satisfies (|G|+1)/3 ≤ Δ< |G|/2 and none of its components is a KΔ₊₁.