Mutual-visibility colouring with two colours is NP-complete for every fixed diameter

@misc{chaubal2026mutualvisibility,
  title = {{Mutual-visibility colouring with two colours is NP-complete for every fixed diameter}},
  author = {Siddhesh Chaubal},
  howpublished = {arXiv},
  year = {2026},
  month = nov,
  doi = {10.48550/arxiv.2611.01012},
  eprint = {2611.01012},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.01012},
}

TY  - UNPB
TI  - Mutual-visibility colouring with two colours is NP-complete for every fixed diameter
AU  - Siddhesh Chaubal
PY  - 2026
DA  - 2026/11/01
PB  - arXiv
DO  - 10.48550/arxiv.2611.01012
UR  - https://arxiv.org/abs/2611.01012
AB  - 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)≤ 2 for graphs of diameter four. We show that the problem remains NP-complete for graphs of diameter d, for every fixed d≥2; diameter two is the smallest diameter for which the problem is non-trivial. The proof rests on a reformulation of χ_μ(G)≤ 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.
ER  -