跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv: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
arXiv ↗PDF ↗

摘要

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≥4k\ge4. 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 O(n+m)O(n+m) time, where nn and mm count the vertices and edges. For strongly chordal graphs with clique-tree separators of size at most ss, we give an exact algorithm in n2O(s+1)n^{2^{O(s+1)}} time, with no bound on the clique number.

AI 论文解读

基于摘要 · 非全文审阅

此版本尚未生成 AI 解读。解读由后台任务生成并按论文版本保存,登录后共享已有结果。

版本差异

目前只收录了一个版本。收录下一版后,可以对照标题、作者、分类和摘要。

观测到的版本

相邻记录可能跳过中间版本;首次发现 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 k≥4k\ge4. 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 O(n+m)O(n+m) time, where nn and mm count the vertices and edges. For strongly chordal graphs with clique-tree separators of size at most ss, we give an exact algorithm in n2O(s+1)n^{2^{O(s+1)}} time, with no bound on the clique number.

查看此版本解读 →查看此版本原文 ↗