| Title: | Independent mutual-visibility coloring and related concepts |
|---|
| Authors: | ID Brešar, Boštjan (Author)
ID Peterin, Iztok (Author)
ID Samadi, Babak (Author)
ID Yero, Ismael G. (Author) |
|---|
| Files: |  URL - Source URL, visit https://link.springer.com/article/10.1007/s00010-026-01280-y
 PDF - Presentation file, download (596,20 KB)
MD5: 8953B52F351393E2BD5345BC30B9CE8C
|
|---|
| Language: | English |
|---|
| Typology: | 1.01 - Original Scientific Article |
|---|
| Organization: |  IMFM - Institute of Mathematics, Physics, and Mechanics
|
|---|
| Abstract: | 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. |
|---|
| Keywords: | independent mutual visibility, mutual-visibility coloring, independence number, Ramsey number, graph product, diameter 2 graph, geodesic |
|---|
| Publication status: | Published |
|---|
| Publication version: | Version of Record |
|---|
| Publication date: | 01.06.2026 |
|---|
| Year of publishing: | 2026 |
|---|
| Number of pages: | 27 str. |
|---|
| Numbering: | Vol. 100, iss. 3, article no. 48 |
|---|
| PID: | 20.500.12556/DiRROS-29255  |
|---|
| UDC: | 519.17 |
|---|
| ISSN on article: | 0001-9054 |
|---|
| DOI: | 10.1007/s00010-026-01280-y |
|---|
| COBISS.SI-ID: | 276957187 |
|---|
| Note: |
|
|---|
| Publication date in DiRROS: | 05.05.2026 |
|---|
| Views: | 57 |
|---|
| Downloads: | 38 |
|---|
| Metadata: |    |
|---|
|
:
|
Copy citation |
|---|
| | | | Share: |  |
|---|
Hover the mouse pointer over a document title to show the abstract or click
on the title to get all document metadata. |
