Independent mutual-visibility coloring and related concepts
Boštjan Brešar, Iztok Peterin, Babak Samadi, Ismael G. Yero · Aequationes Mathematicae · 2026
Abstract Given a graph G , a subset $$M\subseteq V(G)$$ M ⊆ V ( G ) is a mutual-visibility (MV) set if for every $$u,v\in M$$ u , v ∈ M , there exists a u , v -geodesic whose internal vertices are not in M . We investigate proper vertex colorings of graphs whose color classes are mutual-visibility sets. The main concepts that arise in this investigation are independent mutual-visibility (IMV) sets and vertex partitions into these sets (IMV colorings). The IMV number $$\mu _{i}$$ μ i and the IMV chromatic number $$\chi _{\mu _{i}}$$ χ μ i are defined as maximum and minimum cardinality taken over all IMV sets and IMV colorings, respectively. Along the way, we also continue with the study of MV chromatic number $$\chi _{\mu }$$ χ μ (as the smallest number of sets in a vertex partition into MV sets), which was initiated in an earlier paper. We establish a close connection between the (I)MV chromatic numbers of subdivisions of complete graphs and Ramsey numbers $$R(4^k;2)$$ R ( 4 k ; 2 ) . From the computational point of view, we prove that the problems of computing $$\chi _{\mu _{i}}$$ χ μ i and $$\mu _{i}$$ μ i are NP-complete, and that it is NP-hard to decide whether a graph G satisfies $$\mu _i(G)=\alpha (G)$$ μ i ( G ) = α ( G ) where $$\alpha (G)$$ α ( G ) is the independence number of G . Several tight bounds on $$\chi _{\mu _{i}}$$ χ μ i , $$\chi _{\mu }$$ χ μ and