{
  "id": "2411.12124",
  "version": "v1",
  "published": "2024-11-18T23:30:27.000Z",
  "updated": "2024-11-18T23:30:27.000Z",
  "title": "A note on the mutual-visibility coloring of hypercubes",
  "authors": [
    "Maria Axenovich",
    "Dingyuan Liu"
  ],
  "comment": "4 pages, comments are welcome",
  "categories": [
    "math.CO"
  ],
  "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 $\\chi_{\\mu}(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 has been shown that the maximum size of a mutual-visibility set in $Q_{n}$ is at least $\\Omega(2^{n})$. Klav\\v{z}ar, Kuziak, Valenzuela-Tripodoro, and Yero further asked whether it is true that $\\chi_{\\mu}(Q_{n})=O(1)$. In this note we answer their question in the negative by showing that $$\\omega(1)=\\chi_{\\mu}(Q_{n})=O(\\log\\log{n}).$$",
  "revisions": [
    {
      "version": "v1",
      "updated": "2024-11-18T23:30:27.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "mutual-visibility set",
      "mutual-visibility coloring",
      "color class",
      "dimensional hypercube",
      "internal vertices"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 4,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}