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 Δ and chromatic number r? By considering the Alon-Tarsi number of G, we prove that the paintability of G is at most (1 - 1/4r+1 ) Δ + 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 Δ is sufficiently large, the DP-paintability of G is at most Δ - Ω( √Δ log Δ).
No takes yet. Share an insight, caveat, or question.
Bradshaw et al. (2024) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: