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

- فلوچارت مراحل ورود و ثبت نام در سامانه نشریات علمی وزارت عتف

- راه اندازی سیستم مدیریت نشریات علمی دانشگاه پیام نور

تعداد نشریات	41
تعداد شماره‌ها	1,138
تعداد مقالات	9,757
تعداد مشاهده مقاله	17,850,825
تعداد دریافت فایل اصل مقاله	12,466,224

	A Hybrid Floyd-Warshall and Graph Coloring Algorithm for Finding the Smallest Number of Colors Needed for a Distance Coloring of Graphs
Control and Optimization in Applied Mathematics
مقاله 10، دوره 9، شماره 1، مرداد 2024، صفحه 185-194 اصل مقاله (676.39 K)
نوع مقاله: Research Article
شناسه دیجیتال (DOI): 10.30473/coam.2023.68880.1244
نویسندگان
Hanifa Mosawi¹؛ Mostafa Tavakolli^* ¹؛ Khatere Ghorbani-Moghadam²
¹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‎.
چکیده
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.
کلیدواژه‌ها
p-distance coloring‎؛ ‎p-distance chromatic number‎؛ ‎Graph adjacency matrix‎؛ ‎Hybrid algorithm

مراجع
[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.
آمار تعداد مشاهده مقاله: 435 تعداد دریافت فایل اصل مقاله: 231

سامانه مدیریت نشریات علمی. قدرت گرفته از سیناوب

پیوندهای مفید

اخبار و اعلانات

آمار

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