Equitable colorings of $K_4$-minor-free graphs

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 rath...

Full description

Saved in:
Bibliographic Details
Published in:Journal of graph algorithms and applications 2017-10, Vol.21 (6), p.1091-1105
Main Authors: De Joannis de Verclos, Rémi, Sereni, Jean-Sébastien
Format: Article
Language:English
Subjects:
Combinatorics
Mathematics
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1526-1719
1526-1719
DOI:10.7155/jgaa.00451