Diameter-two graphs whose mutual-visibility chromatic number equals their chromatic number
In the authors' words
A set of vertices of a graph is a mutual-visibility set if every pair of vertices of is joined by a shortest path whose internal vertices avoid , and the mutual-visibility chromatic number is the least number of mutual-visibility sets into which can be partitioned. Klav\v{z}ar, Kuziak, Valenzuela Tripodoro and Yero (2025) proved that whenever 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 of order 11 and diameter two with , and an infinite family of such graphs obtained from by replacing one vertex with pairwise non-adjacent copies of it.
Appeared: Friday, October 30. arXiv. Preprint, not yet peer-reviewed.
Authors' comment: 8 pages, 3 figures. Submitted to Aequationes Mathematicae