2023/06/21 by Ma, Jie, Xu, Rongxing, Zhu, Xuding
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2306.11995
Given positive integers p ≥ k, and a non-negative integer d, we say a graph G is (k,d,p)-choosable if for every list assignment L with |L(v)|≥ k for each v ∈ V(G) and |\bigcupv∈ V(G)L(v)| ≤ p, there exists an L-coloring of G such that each monochromatic subgraph has maximum degree at most d. In particular, (k,0,k)-choosable means k-colorable, (k,0,+∞)-choosable means k-choosable and (k,d,+∞)-choosable means d-defective k-choosable. This paper proves that there are 1-defective 3-choosable graphs that are not 4-choosable, and for any positive integers ℓ ≥ k ≥ 3, and non-negative integer d, there are (k,d, ℓ)-choosable graphs that are not (k,d , ℓ+1)-choosable. These results answer questions asked by Wang and Xu [SIAM J. Discrete Math. 27, 4(2013), 2020-2037], and Kang [J. Graph Theory 73, 3(2013), 342-353], respectively. Our construction of (k,d, ℓ)-choosable but not (k,d , ℓ+1)-choosable graphs generalizes the construction of Král' and Sgall in [J. Graph Theory 49, 3(2005), 177-186] for the case d=0.