New evolutionary operators in coloring DIMACS challenge benchmark graphs

Recently, graph coloring, an NP-complete problem, is an optimization problem generally applied in various applications. The solution to the graph coloring problem is found using different soft computing approaches. This research reveals new stochastic operators in solving graph coloring. In this research, the expected crossovers (c¯) and mutations (m¯) are controlled by the central conflict of the gene sequence and ∆(G), the most significant degree of the graph G. These factors played a role in minimizing the value ofg¯ , the average number of genetic generations, towards achieving stochastic convergence. The simulation results prove that these operators reduce the problem search space by reducing g¯ to bring a near-optimal coloring. The coloring for most benchmark graphs has been obtained with g¯ ϵ [2, ∆(G)/2x], δ(G) ≥ x, δ(G) is the least degree of G. The operators use a smaller population size, N and are employed on different challenge benchmarks and the results are proved better than the state of the art methods. © 2022, The Author(s), under exclusive licence to Bharati Vidyapeeth's Institute of Computer Applications and Management.