In this paper, we prove that for any graph $G$ and any positive integer $m$, $G$ is $(2m,m)$-paintable if and only if $G$ is 2-paintable. It was asked by Zhu in 2009 whether $k$-paintable graphs are $(km,m)$-paintable for any positive integer $m$. Our result answers this question in the affirmative for $k=2$.
@article{10_37236_3876,
author = {Thomas Mahoney and Jixian Meng and Xuding Zhu},
title = {Characterization of \((2m,m)\)-paintable graphs},
journal = {The electronic journal of combinatorics},
year = {2015},
volume = {22},
number = {2},
doi = {10.37236/3876},
zbl = {1311.05068},
url = {http://geodesic.mathdoc.fr/articles/10.37236/3876/}
}
TY - JOUR
AU - Thomas Mahoney
AU - Jixian Meng
AU - Xuding Zhu
TI - Characterization of \((2m,m)\)-paintable graphs
JO - The electronic journal of combinatorics
PY - 2015
VL - 22
IS - 2
UR - http://geodesic.mathdoc.fr/articles/10.37236/3876/
DO - 10.37236/3876
ID - 10_37236_3876
ER -
%0 Journal Article
%A Thomas Mahoney
%A Jixian Meng
%A Xuding Zhu
%T Characterization of \((2m,m)\)-paintable graphs
%J The electronic journal of combinatorics
%D 2015
%V 22
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/3876/
%R 10.37236/3876
%F 10_37236_3876
Thomas Mahoney; Jixian Meng; Xuding Zhu. Characterization of \((2m,m)\)-paintable graphs. The electronic journal of combinatorics, Tome 22 (2015) no. 2. doi: 10.37236/3876
