{"id":"arxiv/2611.01012","url":"https://arxiv.org/abs/2611.01012","tags":["cs.DM","cs.CC","math.CO"],"score":0,"title":"Mutual-visibility colouring with two colours is NP-complete for every fixed diameter","domain":"cs.DM","source":"arxiv","authors":["Siddhesh Chaubal"],"reviews":0,"subject":"cs.DM","summary":"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)$ 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)\\le 2$ for graphs of diameter four. We show that the problem remains NP-complete for graphs of diameter $d$, for every fixed $d\\ge2$; diameter two is the smallest diameter for which the problem is non-trivial. The proof…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-10-31","reactions":{}}