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.
Mini Review
Open Access
June 16, 2022
Graph Coloring Solutions to Queen Graphs
1
School of Computing, SASTRA Deemed University, Thanjavur, India
Publihed in: International Journal of Mathematical, Engineering, Biological and Applied Computing (Volume 1, Issue 1, 2022)
Page(s):
40-41
Received
May 07, 2022
May 07, 2022
Revised
June 06, 2022
June 06, 2022
Accepted
June 14, 2022
June 14, 2022
Published
June 16, 2022
June 16, 2022
Creative Commons
This is an Open Access article, distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution and reproduction in any medium or format, provided the original work is properly cited.
Copyright: Copyright © The Author(s), 2022. Published by Scientific Publications
Abstract
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