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

Thomas Mahoney, Jixian Meng, Xuding Zhu


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


Painting game, on-line list colouring, paint number, fractional paint number

Full Text: