跳到正文
研踪PaperTrail
← 研踪 PaperTrail

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

摘要

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 χμ(G)χ_μ(G) 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 χμ(G)≤2χ_μ(G)\le 2 for graphs of diameter four. We show that the problem remains NP-complete for graphs of diameter d, for every fixed d≥2d\ge2; diameter two is the smallest diameter for which the problem is non-trivial. More generally, for all fixed k≥2k\ge2 and d≥2d\ge2, it is NP-complete to decide whether χμ(G)≤kχ_μ(G)\le k for graphs of diameter d. The proof rests on a reformulation of χμ(G)≤2χ_μ(G)\le 2 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

AI 论文解读

基于摘要 · 非全文审阅

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

版本差异

本站首次收录为 v2,暂无更早版本可对照。

观测到的版本

相邻记录可能跳过中间版本;首次发现 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 χμ(G)χ_μ(G) 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 χμ(G)≤2χ_μ(G)\le 2 for graphs of diameter four. We show that the problem remains NP-complete for graphs of diameter d, for every fixed d≥2d\ge2; diameter two is the smallest diameter for which the problem is non-trivial. More generally, for all fixed k≥2k\ge2 and d≥2d\ge2, it is NP-complete to decide whether χμ(G)≤kχ_μ(G)\le k for graphs of diameter d. The proof rests on a reformulation of χμ(G)≤2χ_μ(G)\le 2 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.

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