Equitable colorings of $K_4$-minor-free graphs
Vol. 21, no. 6, pp. 1091-1105, 2017. Regular paper.
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.
Submitted: March 2017.
Reviewed: July 2017.
Revised: August 2017.
Accepted: October 2017.
Final: October 2017.
Published: October 2017.
Communicated by Anna Lubiw
article (PDF)