Equitable colorings of $K_4$-minor-free graphs

Abstract

We demonstrate that for every positive integer $\Delta$, every $K_4$-minor-free graph with maximum degree $\Delta$ admits an equitable coloring with $k$ colors where $k\ge\frac{\Delta+3}{2}$. This bound is tight and confirms a conjecture by Zhang and Wu. We do not use the discharging method but rather exploit decomposition trees of $K_4$-minor-free graphs.