Independent mutual-visibility coloring and related concepts

Abstract Given a graph G , a subset $$M\subseteq V(G)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>M</mml:mi> <mml:mo>⊆</mml:mo> <mml:mi>V</mml:mi> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> is a mutual-visibility (MV) set if for every $$u,v\in M$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>u</mml:mi> <mml:mo>,</mml:mo> <mml:mi>v</mml:mi> <mml:mo>∈</mml:mo> <mml:mi>M</mml:mi> </mml:mrow> </mml:math> , 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}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>μ</mml:mi> <mml:mi>i</mml:mi> </mml:msub> </mml:math> and the IMV chromatic number $$\chi _{\mu _{i}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>χ</mml:mi> <mml:msub> <mml:mi>μ</mml:mi> <mml:mi>i</mml:mi> </mml:msub> </mml:msub> </mml:math> 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 }$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>χ</mml:mi> <mml:mi>μ</mml:mi> </mml:msub> </mml:math> (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)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>R</mml:mi> <mml:mo>(</mml:mo> <mml:msup> <mml:mn>4</mml:mn> <mml:mi>k</mml:mi> </mml:msup> <mml:mo>;</mml:mo> <mml:mn>2</mml:mn> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> . From the computational point of view, we prove that the problems of computing $$\chi _{\mu _{i}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>χ</mml:mi> <mml:msub> <mml:mi>μ</mml:mi> <mml:mi>i</mml:mi> </mml:msub> </mml:msub> </mml:math> and $$\mu _{i}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>μ</mml:mi> <mml:mi>i</mml:mi> </mml:msub> </mml:math> are NP-complete, and that it is NP-hard to decide whether a graph G satisfies $$\mu _i(G)=\alpha (G)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>μ</mml:mi> <mml:mi>i</mml:mi> </mml:msub> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>=</mml:mo> <mml:mi>α</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> where $$\alpha (G)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>α</mml:mi> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> is the independence number of G . Several tight bounds on $$\chi _{\mu _{i}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>χ</mml:mi> <mml:msub> <mml:mi>μ</mml:mi> <mml:mi>i</mml:mi> </mml:msub> </mml:msub> </mml:math> , $$\chi _{\mu }$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>χ</mml:mi> <mml:mi>μ</mml:mi> </mml:msub> </mml:math> and