{"id":"arxiv/2611.03906","url":"https://arxiv.org/abs/2611.03906","tags":["cs.DM","math.CO"],"score":0,"title":"Proper Conflict-Free Coloring on Structured Graph Classes: Bounds, Exact Algorithms, and Hardness","domain":"cs.DM","source":"arxiv","authors":["Kamal Santra"],"reviews":0,"subject":"cs.DM","summary":"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)\\leq\\pcf(G)\\leqω(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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-11-02","reactions":{}}