Equitable Coloring of Graphs with Intermediate Maximum Degree

Abstract

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 $\Delta =\Delta (G)$ the maximum degree of a vertex in $G$. We prove that a graph $G$ of order at least 6 is equitably $\Delta$-colorable if $G$ satisfies $(|G|+1)/3\le \Delta <|G|/2$ and none of its components is a $K_{\Delta +1}$.

14 pages