International Journal of Mathematical, Engineering, Biological and Applied Computing
Mini Review | Open Access | 10.31586/ijmebac.2022.335

Graph Coloring Solutions to Queen Graphs

Raja Marappan1
1
School of Computing, SASTRA Deemed University, Thanjavur, India

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

  1. 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)
  2. http://cedric.cnam.fr/~porumbed/graphs/
  3. http://dimacs.rutgers.edu/programs/challenge/
  4. 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]
  5. 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]
  6. 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]
  7. 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]
  8. 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

© 2024 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

Citations
Google Scholar 1

If you find this article cited by other articles, please click the button to add a citation.

Article Access Statistics
Article Download Statistics
Article metrics
Views
251
Downloads
107
Citations
1

How to Cite

Marappan, R. (2022). Graph Coloring Solutions to Queen Graphs. International Journal of Mathematical, Engineering, Biological and Applied Computing, 1(1), 40–41. Retrieved from https://www.scipublications.com/journal/index.php/ijmebac/article/view/335
  1. 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)
  2. http://cedric.cnam.fr/~porumbed/graphs/
  3. http://dimacs.rutgers.edu/programs/challenge/
  4. 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]
  5. 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]
  6. 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]
  7. 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]
  8. 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

Citations of