A set S of vertices of a graph G is a mutual-visibility set if every pair of vertices of S is joined by a shortest path whose internal vertices avoid S, and the mutual-visibility chromatic number χ_μ(G) is the least number of mutual-visibility sets into which $V(G)$ can be partitioned. Klavžar, Kuziak, Valenzuela Tripodoro and Yero (2025) proved that χ_μ(G)≤χ(G) whenever G has diameter two, observed that equality holds for complete bipartite graphs, and asked whether there are any other diameter-two graphs attaining equality. We answer this question in the affirmative. We construct a graph G₁₁ of order 11 and diameter two with χ_μ(G₁₁)=χ(G₁₁)=3, and an infinite family of such graphs obtained from G₁₁ by replacing one vertex with pairwise non-adjacent copies of it.
No takes yet. Share an insight, caveat, or question.
Siddhesh Chaubal (2026) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: