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, Š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 \[ κ_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, Škrekovski, and Xu and of Wang and Zhang. We prove that every connected graph $G\ne C_5$ with either $\mathrm{mad}(G)<\frac{12}{5}$ or $\Delta (G)\le 3$ 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.

27 pages, 9 figures