Equitable colorings of $K_4$-minor-free graphs
Journal of graph algorithms and applications, Tome 21 (2017) no. 6, pp. 1091-1105
Cet article a éte moissonné depuis la source Journal of Graph Algorythms and Applications website
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.
Keywords:
Equitable coloring; maximum degree, K4-minor-free graph, Series-parallel graph, Decomposition tree
@article{JGAA_2017_21_6_a5,
author = {R\'emi de Joannis de Verclos and Jean-S\'ebastien Sereni},
title = {Equitable colorings of $K_4$-minor-free graphs},
journal = {Journal of graph algorithms and applications},
pages = {1091--1105},
year = {2017},
volume = {21},
number = {6},
doi = {10.7155/jgaa.00451},
language = {en},
url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00451/}
}
TY - JOUR AU - Rémi de Joannis de Verclos AU - Jean-Sébastien Sereni TI - Equitable colorings of $K_4$-minor-free graphs JO - Journal of graph algorithms and applications PY - 2017 SP - 1091 EP - 1105 VL - 21 IS - 6 UR - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00451/ DO - 10.7155/jgaa.00451 LA - en ID - JGAA_2017_21_6_a5 ER -
%0 Journal Article %A Rémi de Joannis de Verclos %A Jean-Sébastien Sereni %T Equitable colorings of $K_4$-minor-free graphs %J Journal of graph algorithms and applications %D 2017 %P 1091-1105 %V 21 %N 6 %U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00451/ %R 10.7155/jgaa.00451 %G en %F JGAA_2017_21_6_a5
Rémi de Joannis de Verclos; Jean-Sébastien Sereni. Equitable colorings of $K_4$-minor-free graphs. Journal of graph algorithms and applications, Tome 21 (2017) no. 6, pp. 1091-1105. doi: 10.7155/jgaa.00451
Cité par Sources :