Document Type : Research Article
Authors
Department of Applied Mathematics, Faculty of Mathematical Sciences, Ferdowsi University of Mashhad, P.O. Box 1159-91775, Mashhad, Iran.
Abstract
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.
Highlights
- A local search metaheuristic is developed to compute irregular face colorings by assigning distinct color codes to all vertices.
- An integer linear programming (ILP) formulation is employed to validate the accuracy and efficiency of the proposed heuristic, particularly for large and regular graph instances.
- The method provides effective irregular face coloring for fullerene graphs, demonstrating the applicability of combinatorial optimization techniques to molecular structures in chemistry and materials science.
Keywords
- Irregular coloring
- Face coloring
- Linear programming
- Metaheuristic algorithm
- Fullerene graphs
- Planar graphs
Main Subjects
)