Strengthening \((a,b)\)-choosability results to \((a,b)\)-paintability (Q2411512)

Summary: Let \(a,b\in\mathbb{N}\). A graph \(G\) is \((a,b)\)-choosable if for any list assignment \(L\) such that \(|L(v)|\geq a\), there exists a coloring in which each vertex \(v\) receives a set \(C(v)\) of \(b\) colors such that \(C(v)\subseteq L(v)\) and \(C(u)\cap C(w)=\emptyset\) for any \(uw\in E(G)\). In the online version of this problem, on each round, a set of vertices allowed to receive a particular color is marked, and the coloring algorithm chooses an independent subset of these vertices to receive that color. We say \(G\) is \((a,b)\)-paintable if when each vertex \(v\) is allowed to be marked \(a\) times, there is an algorithm to produce a coloring in which each vertex \(v\) receives \(b\) colors such that adjacent vertices receive disjoint sets of colors. We show that every odd cycle \(C_{2k+1}\) is \((a,b)\)-paintable exactly when it is \((a,b)\)-chosable, which is when \(a\geq2b+\lceil b/k\rceil\). \textit{X. Zhu} [Electron. J. Comb. 16, No. 1, Research Paper R127, 16 p. (2009; Zbl 1186.05061)] conjectured that if \(G\) is \((a,1)\)-paintable, then \(G\) is \((am,m)\)-paintable for any \(m\in\mathbb{N}\). The following results make partial progress towards this conjecture. Strengthening results of \textit{Z. Tuza} and \textit{M. Voigt} [J. Graph Theory 22, No. 3, 245--252 (1996; Zbl 0853.05034)], and of \textit{U. Schauz} [Electron. J. Comb. 16, No. 1, Research Paper R77, 18 p. (2009; Zbl 1186.05085)], we prove for any \(m \in \mathbb{N}\) that \(G\) is \((5m,m)\)-paintable when \(G\) is planar. Strengthening work of Tuza and Voigt [loc. cit.], and of \textit{J. Hladky} et al. [Discrete Math. 310, No. 23, 3426--3428 (2010; Zbl 1222.05061)], we prove that for any connected graph \(G\) other than an odd cycle or complete graph and any \(m\in\mathbb{N}\), \(G\) is \((\Delta(G)m,m)\)-paintable.