{"id":"arxiv/2608.10874","url":"https://arxiv.org/abs/2608.10874","tags":["cs.DM","math.CO"],"score":0,"title":"Complexity and algorithms for proper conflict-free coloring in graphs","domain":"cs.DM","source":"arxiv","authors":["Dinabandhu Pradhan","Vaishali Sharma"],"reviews":0,"subject":"cs.DM","summary":"A proper conflict-free (PCF) $k$-coloring of a graph $G$ is a proper $k$-coloring such that there exists a color that appears exactly once in the neighborhood of every non-isolated vertex $v\\in V(G)$. The PCF chromatic number, denoted by $χ_{pcf}(G)$, is the least integer $k$ such that there exists a PCF $k$-coloring of $G$. Given a graph $G$ and a positive integer $k$, PCF $k$-COLORABILITY is to decide whether $G$ admits a PCF $k$-coloring. Ahn et al. [Discrete Appl. Math. 377 (2025) 10-17] proved that PCF $k$-COLORABILITY is NP-complete for bipartite graphs. We strengthen this result by…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-08-11","reactions":{}}