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 NG(u). A graph G is proper conflict-free f-choosable if for every list assignment L with |L(v)|≥ 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 κG:V(G)→ ℕ be defined by κG(v)= 4, & if dG(v)=2, [4pt] dG(v)+1, & if dG(v)≠ 2. They conjectured that every connected graph other than C5 is proper conflict-free κ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≠ C5 with either mad(G)<12/5 or Δ(G)≤3 is proper conflict-free κ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.
Related
- Proper conflict-free degree-choosability of graphs with maximum average degree less than 8/3
- Proper conflict-free choosability of sparse graphs with girth at least seven
- Bounded-Defect Proper Orientations and Graphs on Surfaces
- A Counterexample to the Alon-Krivelevich Conjecture and a New Lower Bound for Choosability of Bipartite Graphs
- Proper Conflict-Free Coloring on Structured Graph Classes: Bounds, Exact Algorithms, and Hardness
BibTeX
@misc{lu2026proper,
title = {{Proper Conflict-Free Choosability for Graphs with Bounded Average Degree}},
author = {Zhijun Lu and Qirui Ying and Huimin Song},
howpublished = {arXiv},
year = {2026},
month = aug,
doi = {10.48550/arxiv.2608.29375},
eprint = {2608.29375},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.29375},
}
RIS
TY - UNPB
TI - Proper Conflict-Free Choosability for Graphs with Bounded Average Degree
AU - Zhijun Lu
AU - Qirui Ying
AU - Huimin Song
PY - 2026
DA - 2026/08/29
PB - arXiv
DO - 10.48550/arxiv.2608.29375
UR - https://arxiv.org/abs/2608.29375
AB - 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)|≥ 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 κ_G:V(G)→ ℕ be defined by κ_G(v)= 4, & if d_G(v)=2, [4pt] d_G(v)+1, & if d_G(v)≠ 2. They conjectured that every connected graph other than C_5 is proper conflict-free κ_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≠ C_5 with either mad(G)<12/5 or Δ(G)≤3 is proper conflict-free κ_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.
ER -