Graph Coloring Solutions to Queen Graphs
Abstract
Graph coloring, an NP-complete problem is used in many real-world applications. The minimum color, that is, the chromatic number of a connected graph is determined using different soft computing strategies. This article gives some of the solutions obtained for queen graphs using evolutionary methods.
1. Introduction
Let G be the connected graph with n vertices and e edges. The chromatic number of G, χ(G) is the least color count required to color the vertex set V(G) such that no two adjacent vertices are assigned with the same integer [1]. χ(G) is determined using different soft computing strategies [2, 3]. This research gives χ(G) and the optimal coloring assignments for some of the queen graphs that are obtained using the soft computing strategies.
2. Queen Graphs Color Assignments
2.1. queen5_5.col
χ(G) = 5
Optimal color assignments:
(3 4 2 5 1 2 5 1 3 4 1 3 4 2 5 4 2 5 1 3 5 1 3 4 2)
(1 2 3 4 5 3 4 5 1 2 5 1 2 3 4 2 3 4 5 1 4 5 1 2 3)
(2 3 4 5 1 4 5 1 2 3 1 2 3 4 5 3 4 5 1 2 5 1 2 3 4)
(3 1 4 5 2 4 5 2 3 1 2 3 1 4 5 1 4 5 2 3 5 2 3 1 4)
(1 2 3 4 5 4 5 1 2 3 2 3 4 5 1 5 1 2 3 4 3 4 5 1 2)
(3 4 1 5 2 1 5 2 3 4 2 3 4 1 5 4 1 5 2 3 5 2 3 4 1)
2.2. queen6_6.col
χ(G) = 7
Optimal color assignments:
(7 1 2 3 4 5 2 3 4 5 6 7 4 5 6 7 1 2 6 7 1 2 3 4 1 2 3 4 5 6 3 4 5 6 7 1)
(5 1 2 3 4 6 2 3 4 6 7 5 4 6 7 5 1 2 7 5 1 2 3 4 1 2 3 4 6 7 3 4 6 7 5 1)
(1 3 6 4 5 7 5 7 2 1 3 6 3 6 4 5 7 2 7 2 1 3 6 4 6 4 5 7 2 1 2 1 3 6 4 5)
(3 2 5 6 7 4 4 6 7 2 1 5 2 5 1 3 6 7 1 4 2 7 5 3 5 7 3 1 4 6 6 1 4 5 3 2)
2.3. queen7_7.col
χ(G) = 7
Optimal color assignments:
(5 6 1 3 4 7 2 7 2 5 6 1 3 4 3 4 7 2 5 6 1 6 1 3 4 7 2 5 2 5 6 1 3 4 7 4 7 2 5 6 1 3 1 3 4 7 2 5 6)
(1 2 3 4 5 6 7 3 4 5 6 7 1 2 5 6 7 1 2 3 4 7 1 2 3 4 5 6 2 3 4 5 6 7 1 4 5 6 7 1 2 3 6 7 1 2 3 4 5)
2.4. queen8_8.col
χ(G) = 9
Optimal color assignments:
(1 2 3 4 5 6 7 8 3 4 1 6 8 2 5 9 5 8 9 7 4 3 6 2 6 7 2 5 9 8 1 4 2 5 6 1 3 4 9 7 9 3 4 2 6 7 8 5 8 6 7 9 1 5 2 3 7 1 5 8 2 9 4 6)
3. Conclusions
This article presented some of the solutions obtained for queen graphs using evolutionary methods.
References
- Michael R. Garey; David S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, New York (1979)
- http://cedric.cnam.fr/~porumbed/graphs/
- http://dimacs.rutgers.edu/programs/challenge/
- R. Marappan and G. Sethumadhavan, "A New Genetic Algorithm for Graph Coloring," 2013 Fifth International Conference on Computational Intelligence, Modelling and Simulation, 2013, pp. 49-54, doi: 10.1109/CIMSim.2013.17.[CrossRef]
- G. Sethumadhavan and R. Marappan, "A genetic algorithm for graph coloring using single parent conflict gene crossover and mutation with conflict gene removal procedure," 2013 IEEE International Conference on Computational Intelligence and Computing Research, 2013, pp. 1-6, doi: 10.1109/ICCIC.2013.6724190.[CrossRef]
- Marappan, R., Sethumadhavan, G. Solution to Graph Coloring Using Genetic and Tabu Search Procedures. Arab J Sci Eng 43, 525–542 (2018). https://doi.org/10.1007/s13369-017-2686-9[CrossRef]
- Marappan, R.; Sethumadhavan, G. Complexity Analysis and Stochastic Convergence of Some Well-known Evolutionary Operators for Solving Graph Coloring Problem. Mathematics 2020, 8, 303. https://doi.org/10.3390/math8030303[CrossRef]
- Marappan, R., Sethumadhavan, G. Solving Graph Coloring Problem Using Divide and Conquer-Based Turbulent Particle Swarm Optimization. Arab J Sci Eng (2021). https://doi.org/10.1007/s13369-021-06323-x
Copyright
© 2025 by author and Scientific Publications. This is an open access article and the related PDF distributed under the Creative Commons Attribution License which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
Article Metrics
If you find this article cited by other articles, please click the button to add a citation.