Proper Conflict-Free Coloring on Structured Graph Classes: Bounds, Exact Algorithms, and Hardness
Abstract
A proper conflict-free coloring is a proper vertex coloring in which every non-isolated vertex has a neighbor whose color appears exactly once in its open neighborhood. We study this coloring on chordal and ordered bipartite graph classes. For well-partitioned chordal graphs, we prove the tight bound ω(G)≤pcf(G)≤ω(G)+1 and give an O(n2) construction from a partition tree. Every assignment of lists of at least ω(G)+1 colors also admits a PCF coloring that respects the lists. Deciding whether ω(G) colors suffice is NP-complete, even when the partition tree is a star. This also proves NP-completeness on chordal graphs when the number of colors is part of the input. For interval graphs, we prove that lists of size ω(G)+1 always suffice, improving the previous ordinary-coloring bound of ω(G)+2. We use matchings to characterize when ω(G) colors suffice and give an endpoint algorithm taking 2O(ω(G)2)nO(1) time. We also characterize the exact value when the clique number is at most three and give a linear-time algorithm from sorted interval endpoints. For biconvex graphs, we prove a tight five-color bound and give a direct exact algorithm taking O(n33) time. For bipartite permutation graphs, a smaller dynamic program gives an exact O(n17) algorithm. Finally, if a bipartite graph is convex over an ordered shore X, we prove the sharp bound pcf(G)≤⌈log2(|X|+1)⌉+3 and construct a coloring in linear time from the order.
Related
- Double-Partition Coloring problem: a unified approach for conflict-free coloring of hypergraphs and other coloring problems in graphs
- List 3-Coloring in tame classes of graphs in quasipolynomial time
- Dominated Coloring of Some Classes of Perfect and Unicyclic Graphs
- Integer Maximization over ℓp Balls: Hardness and Exact Algorithms
- bayprior: Structured Bayesian Prior Elicitation, Conflict Diagnostics, and Regulatory Reporting
BibTeX
@misc{santra2026proper,
title = {{Proper Conflict-Free Coloring on Structured Graph Classes: Bounds, Exact Algorithms, and Hardness}},
author = {Kamal Santra},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.03906},
eprint = {2611.03906},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.03906},
note = {CC BY-NC-SA 4.0},
}
RIS
TY - UNPB
TI - Proper Conflict-Free Coloring on Structured Graph Classes: Bounds, Exact Algorithms, and Hardness
AU - Kamal Santra
PY - 2026
DA - 2026/11/02
PB - arXiv
DO - 10.48550/arxiv.2611.03906
UR - https://arxiv.org/abs/2611.03906
AB - A proper conflict-free coloring is a proper vertex coloring in which every non-isolated vertex has a neighbor whose color appears exactly once in its open neighborhood. We study this coloring on chordal and ordered bipartite graph classes. For well-partitioned chordal graphs, we prove the tight bound ω(G)≤pcf(G)≤ω(G)+1 and give an O(n^2) construction from a partition tree. Every assignment of lists of at least ω(G)+1 colors also admits a PCF coloring that respects the lists. Deciding whether ω(G) colors suffice is NP-complete, even when the partition tree is a star. This also proves NP-completeness on chordal graphs when the number of colors is part of the input. For interval graphs, we prove that lists of size ω(G)+1 always suffice, improving the previous ordinary-coloring bound of ω(G)+2. We use matchings to characterize when ω(G) colors suffice and give an endpoint algorithm taking 2^O(ω(G)^2)n^O(1) time. We also characterize the exact value when the clique number is at most three and give a linear-time algorithm from sorted interval endpoints. For biconvex graphs, we prove a tight five-color bound and give a direct exact algorithm taking O(n^33) time. For bipartite permutation graphs, a smaller dynamic program gives an exact O(n^17) algorithm. Finally, if a bipartite graph is convex over an ordered shore X, we prove the sharp bound pcf(G)≤⌈log_2(|X|+1)⌉+3 and construct a coloring in linear time from the order.
ER -