Graph Coloring Problem: Two Novel Evolutionary Formulations

Title: Graph Coloring Problem: Two Novel Evolutionary Formulations

Abstract: This research introduces two novel evolutionary formulations for the graph coloring problem. The first formulation is based on the relationship between a graph's chromatic number and its acyclic orientations. It views such orientations as individuals and evolves them using heavily structured evolutionary operators. The second formulation does not tackle one graph at a time but aims to evolve a "program" to color all graphs with similar attributes. The resulting heuristics were tested on DIMACS Implementation Challenge benchmark graphs and found to be competitive.

Main Research Question: Can novel evolutionary formulations improve the efficiency of solving the graph coloring problem?

Methodology: The researchers proposed two novel evolutionary formulations for the graph coloring problem. The first formulation is based on the acyclic orientations of a graph, viewing them as individuals and evolving them with heavily structured evolutionary operators. The second formulation focuses on evolving a "program" to color all graphs with similar attributes.

Results: The heuristics resulting from these formulations were tested on DIMACS Implementation Challenge benchmark graphs and found to be competitive when compared to other heuristics.

Implications: These novel evolutionary formulations provide new approaches to solving the graph coloring problem. While they may not always provide the optimal solution, they offer improved efficiency and can be particularly useful for large-scale graphs. Additionally, these formulations can serve as a basis for further research and development in the field.

Link to Article: https://arxiv.org/abs/0309039v1 Authors: arXiv ID: 0309039v1