A Hybrid Floyd-Warshall and Graph Coloring Algorithm for Finding the Smallest Number of Colors Needed for a Distance Coloring of Graphs

Mosawi, Hanifa; Tavakolli, Mostafa; Ghorbani-Moghadam, Khatere

doi:10.30473/coam.2023.68880.1244

Document Type : Research Article

Authors

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

² Mosaheb Institute of Mathematics‎, ‎Kharazmi University‎, ‎Tehran‎, ‎Iran‎.

10.30473/coam.2023.68880.1244

Abstract

Graph coloring is a crucial area of research in graph theory, with numerous algorithms proposed for various types of graph coloring, particularly graph p-distance coloring‎. In this study, we employ a recently introduced graph coloring algorithm to develop a hybrid algorithm approximating the chromatic number ‎p-distance, where $p$ represents a positive integer number. We apply our algorithm to molecular graphs as practical applications of our findings.

Keywords

Main Subjects

Optimization

References

[1] Anitha, K., Selvam, B., Thirusangu, K. (2016). “Distance-2 chromatic number for the duplicate graph of the Mycielskian graphs”, International Journal of Mathematics of Trends and Technology, 37, 67-72.

[2] Antonucci, S. (1978). “Generalizzazioni del concetto di cromatismo d’un grafo”, Bollettino dell’Unione Matematica Italiana, 15-B, 20-31.

[3] Aslan, M., Baykan, N.A. (2016). “A performance comparison of graph coloring algorithms”, International Journal of Intelligent Systems and Applications in Engineering, 4, 1-7.

[4] Bakaein, S., Tavakoli, M., Ashrafi, A.R., Ori, O. (2018). “Coloring of fullerenes”, Fullerenes, Nanotubes and Carbon Nanostructures, 26, 705-708.

[5] Benmedjdoub, B., Bouchemakh, I. (2019). “2-distance colorings of integer distance graphs”, Discussiones Mathematicae Graph Theory, 39, 589-603.

[6] Bousquet, N., Esperet, L., Harutyunyan, A. (2019). “Exact distance colouring in trees”, Combinatorics, Probability and Computing, 28, 177-186.

[7] DIMACS graph coloring instances, (2016). “Instances homepage on CMU”, [online]. Available: http:mat.gsia.cmu.edu/COLOR/instances.html.

[8] Fertin, G., Godard, E., Raspaud, A. (2003). “Acyclic and k-distance coloring of the grid”, Information Processing Letters, 87(1), 51-58.

[9] Floyd, R.W. (1962). “Algorithm 97: Shortest path”, Communications of the ACM, 5, 345.

[10] Garey, M.R., Johnson, D.S. (1979). “Computers and intractability: A guide to the theory of NP-completeness”, W.H. Freeman and Company, New York, Nantes, France.

[11] Ghazi, Gh., Rahbarnia, F., Tavakoli, M. (2020). “2-Distance chromatic number of some graph products”, Discrete Mathematics, Algorithms and Applications, 12, 2050021.

[12] Gionfriddo, M. (1978). “Sulle colorazioni Ls d’un grafo finito”, Capsula. Un. Stuoia. Ital. (5). v15-A, 444-454.

[13] Gionfriddo, M., Milici, S. (1988).“On the parameter v2(h) ≤ 6h for L2-coloured graphs”, Discrete Mathematics, 68, 107-110.

[14] Jacko, P., Jendrol, S. (2005). “Distance coloring of the hexagonal lattice”, Discussiones Mathematicae Graph Theory, 25(1-2), 151-166.

[15] Kramer, F. (1972). “Brève communication. Sur le nombre chromatique des graphes”, Revue française d’automatique informatique recherche opérationnelle, Mathématique, 6(R1), 67-70.

[16] Kramer, F., Kramer, H. (1969). “Un probleme de coloration des sommets d’un graphe”, CR Académie des sciences Paris A, 268(7), 46-48.

[17] Kramer, F., Kramer, H. (2008). “A survey on the distance-colouring of graphs”, Discrete Mathematics, 308(2-3), 422-426.

[18] Liu, D.D.F. (2008). “From rainbow to the lonely runner: A survey on coloring parameters of distance graphs”, Taiwanese Journal of Mathematics, 12, 851-871.

[19] Molloy, M., Salavatipour, M.R. (2002). “Frequency channel assignment on planar networks”, In Algorithms—ESA 2002: 10th Annual European Symposium Rome, Italy, September 17–21, 2002 Proceedings 10 (pp. 736-747). Springer Berlin Heidelberg.

[20] Mosawi, H., Tavakoli, M., Ghorbani-Moghadam, Kh. (2023). “Solving graph coloring problem using adjacency matrix algorithm”, Accepted by Mathematics Interdisciplinary Research.

[21] S. Sohrabi Hesan, F.Rahbarnia, M. Tavakoli, “The smallest number of colors needed for a coloring of the square of the Cartesian product of certain graphs”, Control and Optimization in Applied Mathematics, 8 (2023) 83-93.

[22] Speranza, F. (1975). “Colorazioni di specie superiore d’un grafo”, Bollettino dell’Unione Matematica Italiana (4) 12, 53–62.

A Hybrid Floyd-Warshall and Graph Coloring Algorithm for Finding the Smallest Number of Colors Needed for a Distance Coloring of Graphs

References

References

Articles in Press, Accepted Manuscript Available Online from 01 March 2024

Articles in Press, Accepted Manuscript
Available Online from 01 March 2024