A variety of the mutual-visibility coloring problem for graphs

Source abstract

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.