A note on the mutual-visibility coloring of hypercubes

Abstract

A subset $M$ of vertices in a graph $G$ is a mutual-visibility set if for any two vertices $u,v\in M$ there exists a shortest $u$-$v$ path in $G$ that contains no elements of $M$ as internal vertices. Let $\ddot{I}{‡}_{\hat{I}}¼(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\in \mathbb{N}$ and $Q_n$ be an $n$-dimensional hypercube. It was proved by the authors that the maximum size of a mutual-visibility set in $Q_n$ is at least $\hat{I}\text{c◯}(2^n)$. Klavžar, Kuziak, Valenzuela-Tripodoro, and Yero further asked whether it is true that $\ddot{I}{‡}_{\hat{I}}¼(Q_n)=O(1)$. In this note we answer their question in the negative by showing that $$\ddot{I}‰(1)=\ddot{I}{‡}_{\hat{I}}¼(Q_n)=O(\log \log n).$$

the manuscript is now included in [arXiv:2402.04791]