2024/11/18 by Maria Axenovich, Dingyuan Liu, Axenovich, Maria +1
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Interconnection Networks and Systems #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.2411.12124
openalex publication_date 2024/11/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A subset M of vertices in a graph G is a mutual-visibility set if for any two vertices u,v∈M there exists a shortest u-v path in G that contains no elements of M as internal vertices. Let χμ(G) be the least number of colors needed to color the vertices of G, so that each color class is a mutual-visibility set. Let n∈ℕ and Qn be an n-dimensional hypercube. It was proved by the authors that the maximum size of a mutual-visibility set in Qn is at least Ω(2n). Klavžar, Kuziak, Valenzuela-Tripodoro, and Yero further asked whether it is true that χμ(Qn)=O(1). In this note we answer their question in the negative by showing that ω(1)=χμ(Qn)=O(loglogn).