Characterization of $(2m,m)$-Paintable Graphs

Abstract

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