Metraipolis › archive › dc_fc300e72cf14
Complexity and algorithms for proper conflict-free coloring in graphs — arXiv:2608.10874
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2608.10874
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-19T06:27:34.092Z
- SHA-256 of the archived text
9a2440cf56bea874bb722d4d57488ceecc5c5d8d6059df7c15764421fe705879- Stable URL of this page
https://metraipolis.com/documento/dc_fc300e72cf14
How to cite
Complexity and algorithms for proper conflict-free coloring in graphs — arXiv:2608.10874 — arXiv (en), https://arxiv.org/abs/2608.10874 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_fc300e72cf14 (Metraipolis archive dc_fc300e72cf14, sha256 9a2440cf56bea874bb722d4d57488ceecc5c5d8d6059df7c15764421fe705879)
BibTeX
@misc{dcfc300e72cf14,
title = {Complexity and algorithms for proper conflict-free coloring in graphs — arXiv:2608.10874},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2608.10874},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_fc300e72cf14; sha256 9a2440cf56bea874bb722d4d57488ceecc5c5d8d6059df7c15764421fe705879},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.10874. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
A proper conflict-free (PCF) $k$-coloring of a graph $G$ is a proper $k$-coloring such that there exists a color that appears exactly once in the neighborhood of every non-isolated vertex $v\in V(G)$. The PCF chromatic number, denoted by $\chi_{pcf}(G)$, is the least integer $k$ such that there exists a PCF $k$-coloring of $G$. Given a graph $G$ and a positive integer $k$, PCF $k$-COLORABILITY is to decide whether $G$ admits a PCF $k$-coloring. Ahn et al. [Discrete Appl. Math. 377 (2025) 10-17] proved that PCF $k$-COLORABILITY is NP-complete for bipartite graphs. We strengthen this result by proving that PCF $k$-COLORABILITY is NP-complete for perfect elimination bipartite graphs, which is a proper subclass of bipartite graphs. We also show that the PCF chromatic number of a graph cannot be approximated within $O(n^{1-\varepsilon})$ unless P=NP, for any $\varepsilon>0$. On the positive side, we provide linear-time algorithms for PCF $k$-COLORABILITY in block graphs, proper interval graphs, chain graphs, and pseudo-split graphs. We show that $\chi_{pcf}(G)\leq \omega(G)+1$ for block graphs, proper interval graphs, and pseudo-split graphs (except $C_5$), and we characterize all graphs for which the equality holds.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-08-12 in math.CO).
Categorie arXiv: Discrete Mathematics (cs.DM) ; Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2608.10874 — 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-10-19T06:20:30.701Z dalla pagina https://arxiv.org/catchup/math.CO/2026-08-12?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).