2024/03/18 by Peter Bradshaw, Bradshaw, Peter, Jinghan A Zeng +1
Computer Science · #05C15 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics
paper · pdf · doi:10.48550/arxiv.2403.11888
openalex publication_date 2024/03/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The online list coloring game is a two-player graph-coloring game played on a graph G as follows. On each turn, a Lister reveals a new color c at some subset S ⊆ V(G) of uncolored vertices, and then a Painter chooses an independent subset of S to which to assign c. As the game is played, the revealed colors at each vertex v ∈ V(G) form a color set L(v), often called a list. The paintability of G measures the minimum value k for which Painter has a strategy to complete a coloring of G in such a way that |L(v)| ≤ k for each vertex v ∈ V(G). The paintability of a graph is an upper bound for its list chromatic number, or choosability. The online list coloring game is a special case of the DP-painting game, which is defined similarly using the setting of DP-coloring. In the DP-painting game, the Lister reveals correspondence covers of a graph G rather than colors, and the Painter chooses independent subsets of these covers. The DP-painting game has a parameter known as DP-paintability which is analogous to paintability. In this paper, we consider upper bounds for the paintability and DP-paintability of a graph G with large maximum degree Δ and chromatic number at most some fixed value r. We prove that the paintability of G is at most (1 - (1)/(4r+1) ) Δ+ 2 and that the DP-paintability of G is at most Δ- Ω( √(Δlog Δ)). We prove our first upper bound using Alon-Tarsi orientations, and we prove our second upper bound by considering the strict type-3 degeneracy parameter recently introduced by Zhou, Zhu, and Zhu.