20.500.12556/DiRROS-29255 Independent mutual-visibility coloring and related concepts Given a graph $G$, a subset $M\subseteq V(G)$ is a mutual-visibility (MV) set if for every $u,v\in 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}$ and the IMV chromatic number $\chi_{\mu_{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)$. From the computational point of view, we prove that the problems of computing $\chi_{\mu_{i}}$ and $\mu_{i}$ are NP-complete, and that it is NP-hard to decide whether a graph $G$ satisfies $\mu_i(G)=\alpha(G)$ where $\alpha(G)$ is the independence number of $G$. Several tight bounds on $\chi_{\mu_{i}}$, $\chi_{\mu}$ and $\mu_{i}$ are given. Exact values/formulas for these parameters in some classical families of graphs are proved. In particular, we prove that $\chi_{\mu_{i}}(T)=\chi_{\mu}(T)$ holds for any tree $T$ of order at least $3$, and determine their exact formulas in the case of lexicographic product graphs. Finally, we give tight bounds on the (I)MV chromatic numbers for the Cartesian and strong product graphs, which lead to exact values in some important families of product graphs. independent mutual visibility mutual-visibility coloring independence number Ramsey number graph product diameter 2 graph geodesic neodvisna vzajemna vidnost barvanje vzajemne vidnosti neodvisnostno število Ramseyevo število produkt grafov graf premera 2 geodetka true false true Angleški jezik Slovenski jezik Neznano 2026-05-05 08:24:12 2026-05-05 08:24:13 2026-05-06 03:51:46 0000-00-00 00:00:00 2026 0 0 27 str. iss. 3, article no. 48 Vol. 100 Jun. 2026 0000-00-00 Zaloznikova Objavljeno NiDoloceno 0000-00-00 0000-00-00 2026-06-01 519.17 0001-9054 10.1007/s00010-026-01280-y 276957187 https://link.springer.com/article/10.1007/s00010-026-01280-y 1 0a948fb7-484b-11f1-969d-001a4af901a5 https://dirros.openscience.si/Dokument.php?lang=slv&id=43774 s00010-026-01280-y.pdf s00010-026-01280-y.pdf 1 8953B52F351393E2BD5345BC30B9CE8C d4ce163302b39b212588e3968d9b5019cddeb743e6fe12cbb02d61920961d555 590c8401-484b-11f1-969d-001a4af901a5 https://dirros.openscience.si/Dokument.php?lang=slv&id=43775 Inštitut za matematiko, fiziko in mehaniko 0 0 0