{"id":"arxiv/2611.08534","url":"https://arxiv.org/abs/2611.08534","tags":["cs.DM","math.CO"],"score":0,"title":"Proper Conflict-Free Coloring of Undirected Path, Chordal Bipartite, and Strongly Chordal Graphs","domain":"cs.DM","source":"arxiv","authors":["Gautam K. Das","Kamal Santra"],"reviews":0,"subject":"cs.DM","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-11-04","reactions":{}}