Paperlane

no. 12 · Tuesday 10 November 2026

Proper conflict-free degree-choosability of graphs with maximum average degree less than $8/3$

Huijuan Xu

math.CO · v3

Abstract

A proper coloring $\varphi$ of a graph $G$ is called proper conflict-free if, for every non-isolated vertex $v$, some color appears exactly once in its open neighborhood $N_G(v)$. For a nonnegative integer $k$, a graph $G$ is proper conflict-free $(\mathrm{degree}+k)$-choosable if, for every list assignment $L$ satisfying $|L(v)|\ge d_G(v)+k$ for each $v\in V(G)$, there exists a proper conflict-free coloring $\varphi$ of $G$ with $\varphi(v)\in L(v)$ for each $v\in V(G)$. We prove that every connected graph other than the $5$-cycle $C_5$ with maximum average degree less than $8/3$ is proper conflict-free $(\mathrm{degree}+2)$-choosable. This improves the maximum average degree bound $18/7$ of Kashima, Škrekovski and Xu, and removes the assumption $g(G)\ge7$ from the $8/3$ theorem of Qi, Song and Cao. We also show that the $(\mathrm{degree}+2)$ list-size bound is best possible for graphs with maximum average degree arbitrarily close to $8/3$ from below. As an immediate consequence, our theorem implies that every planar graph of girth at least $8$ is proper conflict-free $(\mathrm{degree}+2)$-choosable.

fields
Combinatorics
pdf ↗ page arXiv:2610.41668 ↗