RT journal article
T1 Coloring the vertices of a graph with mutual-visibility property
A1 Klavžar, Sandi
A1 Kuziak, Dorota
A1 Valenzuela Tripodoro, Juan Carlos
A1 González Yero, Ismael
A2 Matemáticas
K1 graph coloring
K1 mutual-visibility set
K1 mutual-visibility chromatic number
K1 graph product
K1 diameter two graph
AB Given a graph G, a mutual-visibility coloring of G is a coloring of the vertices of G satisfying thefollowing. Two vertices x y ∈ V(G), can be colored with the same color, if there is a shortest x y, -path whoseinternal vertices have different colors than x and y. The smallest number of colors among all mutual-visibilitycolorings of G is the mutual-visibility chromatic number of G, which is denoted by χ (G)μ . Relationshipsbetween χ (G)μ and its two parent ones, the chromatic number and the mutual-visibility number, are presented.Graphs of diameter two are considered, and in particular, the asymptotic growth of the mutualvisibilitynumber of the Cartesian product of complete graphs is determined. A greedy algorithm that findsa mutual-visibility coloring is designed, and several possible scenarios on its efficiency are discussed. Severalbounds are given in terms of other graph parameters such as the diameter, the order, the maximum degree,the degree of regularity of regular graphs, and/or the mutual-visibility number. For the corona products,it is proved that the value of its mutual-visibility chromatic number depends on that of the first factor ofthe product. Graphs G for which χ (G) =μ 2 are also considered.
SN 2391-5455
YR 2025
FD 2025-07-31
LK http://hdl.handle.net/10498/39031
UL http://hdl.handle.net/10498/39031
LA eng
DS Repositorio Institucional de la Universidad de Cádiz
RD 21-sep-2026