Solving Graph Coloring Problem Using Graph Adjacency Matrix Algorithm

Document Type : Original Scientific Paper

Authors

1 ‎Department of Applied Mathematics‎, ‎‎Faculty of Mathematical Sciences, ‎Ferdowsi University of Mashhad‎, ‎P.O‎. ‎Box 1159‎, ‎Mashhad 91775‎, ‎I‎. ‎R‎. ‎Iran

2 Mosaheb Institute of Mathematics, Kharazmi University, Tehran, I. R. Iran

Abstract

‎Graph coloring is the assignment of one color to each vertex of a graph so that two adjacent vertices are not of the same color‎. ‎The graph coloring problem (GCP) is a matter of combinatorial optimization‎, ‎and the goal of GCP is determining the chromatic number $\chi(G)$‎. ‎Since GCP is an NP-hard problem‎, ‎then in this paper‎, ‎we propose a new approximated algorithm for finding the coloring number (it is an approximation of chromatic number) by using a graph adjacency matrix to colorize or separate a graph‎. ‎To prove the correctness of the proposed algorithm‎, ‎we implement it in MATLAB software‎, ‎and for analysis in terms of solution and execution time‎, ‎we compare our algorithm with some of the best existing algorithms that are already implemented in MATLAB software‎, ‎and we present the results in tables of various graphs‎. ‎Several available algorithms used the largest degree selection strategy‎, ‎while our proposed algorithm uses the graph adjacency matrix to select the vertex that has the smallest degree for coloring‎. ‎We provide some examples to compare the performance of our algorithm to other available methods‎. ‎We make use of the Dolan-Mor'e performance profiles to assess the performance of the numerical algorithms‎, ‎and demonstrate the efficiency of our proposed approach in comparison with some existing methods‎.

Keywords

Main Subjects

References

[1] J. L. Gross, J. Yellen and M. Anderson, Graph Theory and its Applications, Chapman and Hall/CRC, (2018).
[2] F. Ge, Z. Wei, Y. Tian and Z. Huang, Chaotic ant swarm for graph coloring, IEEE international conference on intelligent comput ing and intelligent systems, Xiamen, China, 2010 (2010) 512 - 516, https://doi.org/10.1109/ICICISYS.2010.5658530.
[3] D. J. A. Welsh and M. B. Powell, An upper bound for the chromatic number of a graph and its application to timetabling problems, Comput J. 10 (1967) 85-86, https://doi.org/10.1093/comjnl/10.1.85.
[4] I. M. Díaz and P. Zabala, A generalization of the graph coloring problem, Investig. Oper. 8 (1999) 167 - 184.
[5] M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman (1979).
[6] B. H. Gwee, M. H. Limand and J. S. Ho, Solving four colouring map problem using genetic algorithm, Proceedings of First New Zealand International Two-Stream Conference on Artificial Neural Networks and Expert Systems, Dunedin, New Zealand, (1993) 332-333.
[7] K. A. Dowsland and J. M. Thompson, Ant colony optimization for the examination scheduling problem, J. Oper. Res. Soc. 56 (2005) 426-438, https://doi.org/10.1057/palgrave.jors.2601830.
[8] N. Chmait and K. Challita, Using simulated annealing and ant-colony optimization algorithms to solve the scheduling problem, Comput. Sci. Inf. Tech. 1 (2013) 208-224, https://doi.org/10.13189/csit.2013.010307.
[9] G. J. Chaitin, M. A. Auslander, A. K. Chandra, J. Cocke, M. E. Hopkins and P. W. Markstein, Register allocation via coloring, Comput. Lang. 6 (1981) 47-57, https://doi.org/10.1016/0096-0551(81)90048-5.
[10] F. C. Chow and J. L. Hennessy, The priority based coloring approach to register allocation, ACM Trans. Program. Lang. Syst. 12 (1990) 501-536, https://doi.org/10.1145/88616.88621.
[11] W. K. Hale, Frequency assignment: theory and applications, in Proceedings of the IEEE 68 (1980) 1497-1514. https://doi.org/10.1109/PROC.1980.11899.
[12] S. Mahmoudi and S. Lotfi, Modified cuckoo optimization algorithm (MCOA) to solve graph coloring problem, Appl. Soft Comput. 33 (2015) 48-64, https://doi.org/10.1016/j.asoc.2015.04.020.
[13] A. Hertz and D. de Werra, Using tabu search techniques for graph coloring, Computing 39 (1987) 345-351, https://doi.org/10.1007/BF02239976.
[14] M. Chams, A. Hertz and D. de Werra, Some experiments with simulated annealing for coloring graphs, European J. Oper. Res. 32 (1987) 260-266, https://doi.org/10.1016/S0377-2217(87)80148-0.
[15] S. Ahn, S. Lee and T. Chung, Modified ant colony system for coloring graphs, information, communications and signal processing, 2003 and fourth pacificrim conference on multimedia, Proceedings of the joint conference of the fourth international conference on, 1849-1853, (2003).
[16] H. Al-Omari and K. E. Sabri, New graph coloring algorithms, American journal of mathematics and statistics 2 (2006) 439-441.
[17] F. T. Leighton, A graph coloring algorithm for large scheduling problems, J. Res. Nat. Bur. Standards, 84 (1979) 489- 506.
[18] D. Brélaz, New methods to color the vertices of a graph, Comm. ACM 22 (1979) 251-256, https://doi.org/10.1145/359094.359101.
[19] C. Dimacs, graph coloring instances, (2016) instances homepage on CMU. [online]. Available: http:mat.gsia.cmu.edu/COLOR/instances.html.
[20] P. T. Lima, E. J. van Leeuwen and M. van der Wegen, Algorithms for the rainbow vertex coloring problem on graph classes, Theoret. Comput. Sci. 887 (2021) 122-142, https://doi.org/10.1016/j.tcs.2021.07.009.
[21] S. M. Douiri and S. Elbernoussi, Solving the graph coloring problem via hybrid genetic algorithms, J. King Saud Univ. Eng. Sci. 27 (2015) 114-118, https://doi.org/10.1016/j.jksues.2013.04.001.
[22] M. Aslan and N. A. Baykan, A performance comparison of graph coloring algorithms, Int. J. Intell. Syst. Appl. Eng. 4 (2016) 1-7.
[23] E. D. Dolan and J. J. Moré, Benchmarking optimization software with performance profiles, Math. Program. 91 (2002) 201-213, https://doi.org/10.1007/s101070100263.
[24] K. Balasubramanian, O. Ori, F. Cataldo, A. R. Ashrafi and M. V. Putz, Face colorings and chiral face colorings of icosahedral giant fullerenes: C80 to C240, Fuller. Nanotub. Carbon Nanostructures 29 (2021) 1-12,
https://doi.org/10.1080/1536383X.2020.1794853.
Mathematics Interdisciplinary Research
Volume 9, Issue 2
June 2024
Pages 215-236

Files

Share

How to cite

Statistics