A note on the mutual-visibility coloring of hypercubes
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866911547542994944 |
|---|---|
| author | Axenovich, Maria Liu, Dingyuan |
| author_facet | Axenovich, Maria Liu, Dingyuan |
| contents | 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 $χ_μ(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 $Ω(2^{n})$. Klavžar, Kuziak, Valenzuela-Tripodoro, and Yero further asked whether it is true that $χ_μ(Q_{n})=O(1)$. In this note we answer their question in the negative by showing that $$ω(1)=χ_μ(Q_{n})=O(\log\log{n}).$$ |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_12124 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A note on the mutual-visibility coloring of hypercubes Axenovich, Maria Liu, Dingyuan Combinatorics 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 $χ_μ(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 $Ω(2^{n})$. Klavžar, Kuziak, Valenzuela-Tripodoro, and Yero further asked whether it is true that $χ_μ(Q_{n})=O(1)$. In this note we answer their question in the negative by showing that $$ω(1)=χ_μ(Q_{n})=O(\log\log{n}).$$ |
| title | A note on the mutual-visibility coloring of hypercubes |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2411.12124 |