On Two problems of defective choosability

Abstract

Given positive integers $p\ge 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)|\ge k$ for each $v\in V(G)$ and $|{\bigcup }_{v\in V(G)}L(v)|\le 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,+\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 $\ell \ge k\ge 3$, 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ál' and Sgall in [J. Graph Theory 49, 3(2005), 177-186] for the case $d=0$.

12 pages, 4 figures