Equitable colorings of $K_4$-minor-free graphs
Rémi de Joannis de Verclos, Jean‐Sébastien Sereni · Journal of Graph Algorithms and Applications · 2017
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.