Genetic Algorithm Modeling and Analysis of Acyclic Coloring in High Chromatic Graphs

The acyclic coloring problem, a specialized area within graph coloring, has numerous applications across diverse fields. It involves assigning colors to the vertices of a graph such that no two adjacent vertices share the same color and no bichromatic cycles exist. This problem becomes particularly challenging in high chromatic graphs. In this paper, we introduce a genetic algorithm (GA) with structure-aware selection, crossover, and mutation operators to enhance performance on some benchmark graphs having high chromatic numbers. Compared to the state-of-the-art methods, the proposed GA achieves a 5% to 12.5% reduction in the acyclic chromatic number. Success rates remain high, exceeding 90% for queen graphs, 80% to 90% for Leighton graphs, and 70% to 80% for random graphs. High crossover rates, approximately 17000 to 20000 on an average, maintain diversity, while adaptive mutation strategies enhance convergence. These findings highlight the advantage of integrating structural awareness into evolutionary algorithms for efficient acyclic coloring solutions.