← 研踪 PaperTrailarXiv:2611.01012 · v2
Mutual-visibility k-colouring is NP-complete for every fixed diameter
首次提交 2026-10-31 22:55
版本更新 2026-11-05 21:19
雷达观测 2026-11-06 12:09
摘要
A mutual-visibility set in a graph G is a set S of vertices such that any two vertices of S are connected by a shortest path with no internal vertex in S, and the mutual-visibility chromatic number is the minimum number of mutual-visibility sets needed to partition V(G). Babu, Di Stefano and Lakshmanan showed that it is NP-complete to decide whether for graphs of diameter four. We show that the problem remains NP-complete for graphs of diameter d, for every fixed ; diameter two is the smallest diameter for which the problem is non-trivial. More generally, for all fixed and , it is NP-complete to decide whether for graphs of diameter d. The proof rests on a reformulation of for diameter-two graphs as the 2-colourability of an associated hypergraph, and on a reduction from 2-colourability of 3-uniform hypergraphs without short cycles.
作者备注:9 pages, 1 figure. v2: extended to any fixed number k of colours; new title
观测到的版本
相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。
v2 · 2026-11-05 21:19 · 最新观测版本
Mutual-visibility k-colouring is NP-complete for every fixed diameter
A mutual-visibility set in a graph G is a set S of vertices such that any two vertices of S are connected by a shortest path with no internal vertex in S, and the mutual-visibility chromatic number is the minimum number of mutual-visibility sets needed to partition V(G). Babu, Di Stefano and Lakshmanan showed that it is NP-complete to decide whether for graphs of diameter four. We show that the problem remains NP-complete for graphs of diameter d, for every fixed ; diameter two is the smallest diameter for which the problem is non-trivial. More generally, for all fixed and , it is NP-complete to decide whether for graphs of diameter d. The proof rests on a reformulation of for diameter-two graphs as the 2-colourability of an associated hypergraph, and on a reduction from 2-colourability of 3-uniform hypergraphs without short cycles.
查看此版本解读 →查看此版本原文 ↗