PreprintarXiv licencearXiv
Proper conflict-free choosability of sparse graphs with girth at least seven
Abstract
A proper conflict-free coloring of a graph is a proper vertex coloring in which every non-isolated vertex has a color appearing exactly once in its neighborhood. A graph G is proper conflict-free (degree+2)-choosable if every list assignment L with |L(v)|≥ dG(v)+2 for each v∈ V(G) admits such a coloring from the lists. We prove that every graph with girth at least $7$ and maximum average degree less than 8/3 is proper conflict-free (degree+2)-choosable. Consequently, every planar graph of girth at least $8$ has this property, improving the previously established sufficient girth bound of $9$.
Related
- Proper conflict-free degree-choosability of graphs with maximum average degree less than 8/3
- Proper Conflict-Free Choosability for Graphs with Bounded Average Degree
- A Counterexample to the Alon-Krivelevich Conjecture and a New Lower Bound for Choosability of Bipartite Graphs
- Unbalanced distance-biregular graphs with girth deficiency two
- A Spectral Local-to-Global Principle for Spin Systems on Graphs with Girth At Least Five
BibTeX
@misc{qi2026proper,
title = {{Proper conflict-free choosability of sparse graphs with girth at least seven}},
author = {Xingqin Qi and Huimin Song and Zhulou Cao},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.11249},
eprint = {2609.11249},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.11249},
}
RIS
TY - UNPB
TI - Proper conflict-free choosability of sparse graphs with girth at least seven
AU - Xingqin Qi
AU - Huimin Song
AU - Zhulou Cao
PY - 2026
DA - 2026/09/27
PB - arXiv
DO - 10.48550/arxiv.2609.11249
UR - https://arxiv.org/abs/2609.11249
AB - A proper conflict-free coloring of a graph is a proper vertex coloring in which every non-isolated vertex has a color appearing exactly once in its neighborhood. A graph G is proper conflict-free (degree+2)-choosable if every list assignment L with |L(v)|≥ d_G(v)+2 for each v∈ V(G) admits such a coloring from the lists. We prove that every graph with girth at least $7$ and maximum average degree less than 8/3 is proper conflict-free (degree+2)-choosable. Consequently, every planar graph of girth at least $8$ has this property, improving the previously established sufficient girth bound of $9$.
ER -