← 研踪 PaperTrailarXiv:2611.08534 · v1
Proper Conflict-Free Coloring of Undirected Path, Chordal Bipartite, and Strongly Chordal Graphs
首次提交 2026-11-05 03:54
版本更新 2026-11-05 03:54
雷达观测 2026-11-09 10:17
摘要
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 . For strongly chordal graphs, reverse simple elimination gives a constructive upper bound of one more than the clique number. We obtain exact polynomial-time algorithms under several conditions on the maximum cliques, including when they induce a connected subtree of a clique tree. For strictly chordal graphs we characterize the optimum and construct an optimal coloring in time, where and count the vertices and edges. For strongly chordal graphs with clique-tree separators of size at most , we give an exact algorithm in time, with no bound on the clique number.
观测到的版本
相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-05 03:54 · 最新观测版本
Proper Conflict-Free Coloring of Undirected Path, Chordal Bipartite, and Strongly Chordal Graphs
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 . For strongly chordal graphs, reverse simple elimination gives a constructive upper bound of one more than the clique number. We obtain exact polynomial-time algorithms under several conditions on the maximum cliques, including when they induce a connected subtree of a clique tree. For strictly chordal graphs we characterize the optimum and construct an optimal coloring in time, where and count the vertices and edges. For strongly chordal graphs with clique-tree separators of size at most , we give an exact algorithm in time, with no bound on the clique number.
查看此版本解读 →查看此版本原文 ↗