Proper Conflict-Free Coloring of Undirected Path, Chordal Bipartite, and Strongly Chordal Graphs
Abstract
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≥4. 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 n2O(s+1) time, with no bound on the clique number.
Related
- Maximum Edge Open Packing on AT-Free, Chordal, and Convex Bipartite Graphs
- FirstFit coloring process of random bipartite graphs and an online coloring lower bound in the random order model
- Double-Partition Coloring problem: a unified approach for conflict-free coloring of hypergraphs and other coloring problems in graphs
- (2,ℱ)-Avoiding Coloring and B-Coloring under Bipartite Exclusions
- Covering Families for DP-Coloring of Cartesian Products with Complete Bipartite Graphs
BibTeX
@misc{das2026proper,
title = {{Proper Conflict-Free Coloring of Undirected Path, Chordal Bipartite, and Strongly Chordal Graphs}},
author = {Gautam K. Das and Kamal Santra},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.08534},
eprint = {2611.08534},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.08534},
note = {CC BY-NC-SA 4.0},
}
RIS
TY - UNPB
TI - Proper Conflict-Free Coloring of Undirected Path, Chordal Bipartite, and Strongly Chordal Graphs
AU - Gautam K. Das
AU - Kamal Santra
PY - 2026
DA - 2026/11/04
PB - arXiv
DO - 10.48550/arxiv.2611.08534
UR - https://arxiv.org/abs/2611.08534
AB - 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≥4. 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.
ER -