On Two problems of defective choosability

arXiv2306.11995MaRDI QIDQ6440934FDOQ6440934

Authors: Jie Ma, Rongxing Xu, Xuding Zhu 

Publication date: 20 June 2023

Abstract: Given positive integers $pgek$, 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)|geqk$ for each $vinV(G)$ and $$, 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,+infty)$-choosable means $k$-choosable and $(k,d,+infty)$-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 $ellgeqkgeq3$, and non-negative integer $d$, there are $(k,d,ell)$-choosable graphs that are not $(k,d,ell+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,ell)$-choosable but not $(k,d,ell+1)$-choosable graphs generalizes the construction of Kr'{a}l' and Sgall in [J. Graph Theory 49, 3(2005), 177-186] for the case $d=0$.

This page was built for publication: On Two problems of defective choosability

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6440934)