Metraipolis › archive › dc_b80e308bf28b

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

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.41668
License (as archived)
CC0-1.0
Archived
2026-11-03T05:44:37.528Z
SHA-256 of the archived text
5e740b48f12f3cc49151f4042f5c980e6367c3936296f346c85fad0518eaf8da
Stable URL of this page
https://metraipolis.com/documento/dc_b80e308bf28b

How to cite

Proper conflict-free degree-choosability of graphs with maximum average degree less than $8/3$ — arXiv:2610.41668 — arXiv (en), https://arxiv.org/abs/2610.41668 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_b80e308bf28b (Metraipolis archive dc_b80e308bf28b, sha256 5e740b48f12f3cc49151f4042f5c980e6367c3936296f346c85fad0518eaf8da)
BibTeX
@misc{dcb80e308bf28b,
  title = {Proper conflict-free degree-choosability of graphs with maximum average degree less than $8/3$ — arXiv:2610.41668},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.41668},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_b80e308bf28b; sha256 5e740b48f12f3cc49151f4042f5c980e6367c3936296f346c85fad0518eaf8da},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.41668. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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. As an immediate consequence, our theorem also yields that every planar graph of girth at least $8$ is proper conflict-free $(\mathrm{degree}+2)$-choosable.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.CO, nuovi lavori del giorno).
Categorie arXiv: Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2610.41668 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-03T05:32:17.001Z dalla pagina https://arxiv.org/list/math.CO/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).