Metraipolis › archive › dc_a4dae89da401

A variety of the mutual-visibility coloring problem for graphs — arXiv:2609.31427

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.31427
License (as archived)
CC0-1.0
Archived
2026-10-08T02:59:17.258Z
SHA-256 of the archived text
3debe11b127a1f07d032480fd25ce4d18163697b4ac7435bb4bca99215202682
Stable URL of this page
https://metraipolis.com/documento/dc_a4dae89da401

How to cite

A variety of the mutual-visibility coloring problem for graphs — arXiv:2609.31427 — arXiv (en), https://arxiv.org/abs/2609.31427 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_a4dae89da401 (Metraipolis archive dc_a4dae89da401, sha256 3debe11b127a1f07d032480fd25ce4d18163697b4ac7435bb4bca99215202682)
BibTeX
@misc{dca4dae89da401,
  title = {A variety of the mutual-visibility coloring problem for graphs — arXiv:2609.31427},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.31427},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_a4dae89da401; sha256 3debe11b127a1f07d032480fd25ce4d18163697b4ac7435bb4bca99215202682},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.31427. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

This paper explores variations of vertex-coloring problems defined on graph visibility properties. It introduces and studies the dual, outer, and total mutual-visibility chromatic numbers, which partition the vertex set of a graph into color classes that preserve specific mutual-visibility conditions called dual, outer or total. The work provides structural conditions under which these chromatic parameters are finite or infinite, and establishes that deciding whether a graph admits a dual, outer, or total mutual-visibility coloring using a given number of colors is NP-complete, even when restricted to two colors. Exact formulas and tight bounds for these chromatic parameters are established across several fundamental graph classes. For block graphs, complete characterizations are provided for the outer and dual mutual-visibility chromatic numbers based on structural invariants such as cut vertices and specific forbidden subgraph structures. On Hamming graphs, the dual and total mutual-visibility chromatic numbers are shown to equal the smaller dimension of the factors, while the outer mutual-visibility chromatic number is proven to equal the star arboricity of a corresponding complete bipartite graph. Finally, the paper examines strong grid graphs, determining exact values for their total, outer, and dual mutual-visibility chromatic numbers. These results demonstrate how the parameter behaviors range from finite constants to infinity depending on the grid dimensions.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-28 in math.CO).
Categorie arXiv: Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2609.31427 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-08T02:28:17.928Z dalla pagina https://arxiv.org/catchup/math.CO/2026-09-28?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).