Mutual-visibility colouring with two colours 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)$ 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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2611.01012
curl -X POST /api/v1/records/arxiv/2611.01012/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.01012/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'