Equitable Coloring of Graphs with Intermediate Maximum Degree

Bor-Liang Chen, Kuo-Ching Huang, Ko-Wei Lih

Published 2014-08-26Version 1

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 \leq \Delta < |G|/2$ and none of its components is a $K_{\Delta +1}$.