In collaboration with Payame Noor University and the Iranian Society of Instrumentation and Control Engineers

Document Type : Research Article


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

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



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.


Main Subjects

[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:
[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.