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 Category: research Comments: 0 Disputed: false Division: cs Mentions: 0 Discussed: 0 Published: 2026-11-04 Page: https://delphi.science/r/arxiv/2611.08534 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…