Proper Conflict-Free Choosability for Graphs with Bounded Average Degree

Abstract

For a graph $G$, a proper coloring of $G$ is called proper conflict-free if for every non-isolated vertex $u$, there is at least one color appearing exactly once in $N_G(u)$. A graph $G$ is proper conflict-free $f$-choosable if for every list assignment $L$ with $|L(v)|\ge f(v)$ for each vertex $v$, $G$ admits a proper conflict-free $L$-coloring. Recently, Kashima, \v{S}krekovski, and Xu proposed a conjecture on proper conflict-free list coloring. For a graph $G$, let $\kappa_G:V(G)\to \mathbb{N}$ be defined by \[ \kappa_G(v)= \begin{cases} 4,&\text{if } d_G(v)=2,\\[4pt] d_G(v)+1,&\text{if } d_G(v)\neq 2. \end{cases} \] They conjectured that every connected graph other than $C_5$ is proper conflict-free $\kappa_G$-choosable. In this paper, we confirm this conjecture in two classes of graphs with bounded average degree, thereby generalizing results of Kashima, \v{S}krekovski, and Xu and of Wang and Zhang. We prove that every connected graph $G\neq C_5$ with either $\operatorname{mad}(G)<\frac{12}{5}$ or $\Delta(G)\le3$ is proper conflict-free $\kappa_G$-choosable. To prove these results, we introduce a method based on systems of proper conflict-free representatives and develop a construction of auxiliary graphs that preserves the maximum average degree bound.