A Metaheuristic and LP-Based Approach to Irregular Face Coloring in Planar Graphs
نویسندگان
1 Department of Applied Mathematics, Faculty of Mathematical Sciences, Ferdowsi University of Mashhad, P.O. Box 1159-91775, Mashhad, Iran.
2 Department of Applied Mathematics, Faculty of Mathematical Sciences, Ferdowsi University of Mashhad, P.O. Box 1159-91775, Mashhad, Iran.
doi
10.30473/coam.2025.75246.1325چکیده
In irregular coloring, each vertex is labeled with a unique color code, a tuple consisting of its assigned color and the number of neighbors in each color class. This work proposes a local search algorithm as a metaheuristic approach to the irregular face coloring problem in planar graphs, with a particular focus on fullerene molecular structures. Additionally, a linear programming model is utilized to validate the performance of the proposed algorithm. The methodology demonstrates efficient solutions for irregular coloring in fullerene graphs, bridging combinatorial optimization with practical applications in chemistry and materials science.
