Mathematics Interdisciplinary Research

Mathematics Interdisciplinary Research

Simulated Annealing and Integer Linear Programming Approaches to Mutual-Visibility Coloring

Articles in Press

Document Type : Original Scientific Paper

Authors
Alireza Masoudi
Mostafa Tavakoli
Zahra Hamed-Labbafian
Department of Applied Mathematics, Faculty of Mathematical Sciences, Ferdowsi University of Mashhad, ‎P‎. ‎O‎. ‎Box 1159-91775‎, ‎Mashhad‎, ‎I‎. ‎R‎. ‎Iran
10.22052/mir.2026.258483.1575
Abstract
‎‎
‎Vertex coloring is a fundamental concept in graph theory‎, ‎where a color is assigned to each vertex‎, ‎and vertices sharing the same color form a color class‎. ‎This paper introduces and investigates a specific type of coloring known as mutual-visibility coloring‎. ‎In this coloring‎, ‎each color class must satisfy the property that for every pair of vertices within that class‎, ‎there exists at least one shortest path between them that contains no other vertex from the same class‎. ‎The primary objective is to find the minimum number of colors required to achieve such a coloring‎, ‎which is known as the mutual-visibility chromatic number‎. ‎To solve this problem‎, ‎this research employs two complementary approaches‎: ‎a heuristic algorithm based on \textit{simulated annealing}‎, ‎which is efficient for exploring the solution space in large graphs‎, ‎and an exact approach using \textit{integer linear programming}‎, ‎which guarantees finding the optimal solution for graphs of smaller dimensions‎.
Keywords
Mutual-visibility coloring&lrm
Simulated annealing algorithm&lrm
, &lrm
Integer linear programming
Subjects
[1] A. Aljohani and G. Sharma, Complete visibility for mobile robots with lights tolerating faults, Int. J. Netw. Comput. 8 (2018) 32-52.
[2] G. A. Di Luna, P. Flocchini, S. G. Chaudhuri, F. Poloni, N. Santoro and G. Viglietta, Mutual visibility by luminous robots without collisions, Inform. and Comput. 254 (2017) 392-418, https://doi.org/10.1016/j.ic.2016.09.005.
[3] G. Di Stefano, Mutual visibility in graphs, Appl. Math. Comput. 419 (2022) #126850, https://doi.org/10.1016/j.amc.2021.126850.
[4] S. Cicerone, G. Di Stefano, S. Klavžar and I. G. Yero, Mutual-visibility in strong products of graphs via total mutual-visibility, Discrete Appl. Math. 358 (2024) 136-146, https://doi.org/10.1016/j.dam.2024.06.038.
[5] D. Korže and A. Vesel, Mutual-visibility sets in Cartesian products of paths and cycles, Results Math. 79 (2024) #116.
[6] D. Kuziak and J. A. Rodríguez-Velázquez, Total mutual-visibility in graphs with emphasis on lexicographic and Cartesian products, Bull. Malays. Math. Sci. Soc. 46 (2023) #197, https://doi.org/10.1007/s40840-023-01590-3.
[7] Z. Hamed-Labbafian, M. Tavakoli, N. Sabeghi and A. Vesel, Mutual visibility in graphs: Hierarchical products, genetic algorithm and some applications, J. Supercomput. 82 (2026) #455, https://doi.org/10.1007/s11227-026-08581-8.
[8] S. Klavžar, D. Kuziak, J. C. V. Tripodoro and I. G. Yero, Coloring the vertices of a graph with mutual-visibility property, Open Math. 23 (2025) #20250193.
[9] S. Babu, G. Di Stefano and A. Lakshmanan S, Mutual-visibility coloring of graphs, (2026), https://arXiv:2512.12251v2.
 
Mathematics Interdisciplinary Research

Articles in Press, Accepted Manuscript
Available Online from 09 November 2026