Metraipolis › archive › dc_09bc7dbc4cac
Proper Conflict-Free Coloring of Undirected Path, Chordal Bipartite, and Strongly Chordal Graphs — arXiv:2611.08534
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2611.08534
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-09T22:43:53.359Z
- SHA-256 of the archived text
8bc0b9bbd878995de263018f1f6305d45440247ced75dafbd181ef78cb76f700- Stable URL of this page
https://metraipolis.com/documento/dc_09bc7dbc4cac
How to cite
Proper Conflict-Free Coloring of Undirected Path, Chordal Bipartite, and Strongly Chordal Graphs — arXiv:2611.08534 — arXiv (en), https://arxiv.org/abs/2611.08534 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_09bc7dbc4cac (Metraipolis archive dc_09bc7dbc4cac, sha256 8bc0b9bbd878995de263018f1f6305d45440247ced75dafbd181ef78cb76f700)
BibTeX
@misc{dc09bc7dbc4cac,
title = {Proper Conflict-Free Coloring of Undirected Path, Chordal Bipartite, and Strongly Chordal Graphs — arXiv:2611.08534},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2611.08534},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_09bc7dbc4cac; sha256 8bc0b9bbd878995de263018f1f6305d45440247ced75dafbd181ef78cb76f700},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.08534. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
A proper conflict-free coloring is a proper coloring in which each nonisolated vertex has a neighbor whose color occurs exactly once in its open neighborhood. We prove that deciding whether the clique number of colors suffices is NP-complete on undirected path graphs, even with a supplied representation by paths in a star. One extra color suffices on every instance in the reduction. We also prove NP-completeness on chordal bipartite graphs for every fixed palette size $k\ge4$. For strongly chordal graphs, reverse simple elimination gives a constructive upper bound of one more than the clique number. We obtain exact polynomial-time algorithms under several conditions on the maximum cliques, including when they induce a connected subtree of a clique tree. For strictly chordal graphs we characterize the optimum and construct an optimal coloring in $O(n+m)$ time, where $n$ and $m$ count the vertices and edges. For strongly chordal graphs with clique-tree separators of size at most $s$, we give an exact algorithm in $n^{2^{O(s+1)}}$ time, with no bound on the clique number.
Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.CO, nuovi lavori del giorno).
Categorie arXiv: Discrete Mathematics (cs.DM) ; Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2611.08534 — 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-09T22:36:32.155Z dalla pagina https://arxiv.org/list/math.CO/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).