Paintability of $r$-chromatic graphs

Peter Bradshaw, Jinghan A Zeng

Published 2024-03-18, updated 2024-07-04Version 3

The paintability of a graph is a coloring parameter defined in terms of an online list coloring game. In this paper we ask, what is the paintability of a graph $G$ of maximum degree $\Delta$ and chromatic number $r$? By considering the Alon-Tarsi number of $G$, we prove that the paintability of $G$ is at most $\left(1 - \frac{1}{4r+1} \right ) \Delta + 2$. We also consider the DP-paintability of $G$, which is defined in terms of an online DP-coloring game. By considering the strict type $3$ degeneracy parameter recently introduced by Zhou, Zhu, and Zhu, we show that when $r$ is fixed and $\Delta$ is sufficiently large, the DP-paintability of $G$ is at most $\Delta - \Omega( \sqrt{\Delta \log \Delta})$.