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

Thomas Mahoney¹

¹Emporia State University

The electronic journal of combinatorics, Tome 24 (2017) no. 4

Résumé

Let $a,b\in\mathbb{N}$. A graph $G$ is $(a,b)$-choosable if for any list assignment $L$ such that $|L(v)|\ge 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\ge2b+\lceil b/k\rceil$. In 2009, Zhu 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 Tuza and Voigt, and of Schauz, we prove for any $m \in \mathbb{N}$ that $G$ is $(5m,m)$-paintable when $G$ is planar. Strengthening work of Tuza and Voigt, and of Hladky, Kral, and Schauz, 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.

Détail

DOI : 10.37236/7163

Classification : 05C15
Mots-clés : graph coloring, paintability, online list coloring