Diameter two graphs discovered with equal coloring and visibility numbers
Diameter-two graphs whose mutual-visibility chromatic number equals their chromatic number
Discrete Mathematics
Summary
This paper looks at a special way of coloring points in a network so that each color group has a visibility property. Earlier work showed that for networks where any two points are close, the minimum number of color groups needed with this visibility matches or is less than normal coloring. The authors found new examples of such networks where these two numbers are exactly equal and created an infinite family from these examples. This helps better understand how visibility and coloring relate in small-diameter networks.
What this means in practice
- •For network designers: Identify specific network structures where visibility-based color partitioning matches traditional coloring, aiding efficient network segmentation for communication protocols.
- •For graph software developers: Build testing tools for graph coloring algorithms using newly constructed graphs with diameter two that have equal mutual-visibility and chromatic numbers.
A theory result. No direct application yet.
Authors
Siddhesh Chaubal
Abstract
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)\leχ(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_{11}$ of order 11 and diameter two with $χ_μ(G_{11})=χ(G_{11})=3$, and an infinite family of such graphs obtained from $G_{11}$ by replacing one vertex with pairwise non-adjacent copies of it.