An Effective Algorithm for Edge Coloring: Malatya Edge Coloring Algorithm

Abstract

In this research, an algorithm offering effective and robust solutions for the edge coloring problem in graph theory is proposed. The edge coloring problem is identified as an NP-hard problem, known for its extensive resolution time and inability to be resolved within polynomial time. The proposed edge coloring algorithm emerges as an efficient greedy method that delivers effective solutions within polynomial time constraints. This developed algorithm employs Malatya centrality values as a decisive factor in the edge coloring process. The Malatya centrality algorithm, a current centrality method, has achieved successful outcomes in various graph problems in the literature. In this study, the algorithm is named the Malatya Edge Coloring Algorithm (MECA). To highlight the success of MECA, its analytical proof has been computationally verified on well-known graphs. Additionally, MECA has been tested on 40 unweighted and undirected lattices, 36 bipartite, 24 multipartite, 8 random, and social network graphs. The results obtained indicate that MECA provides optimal solutions for lattice, bipartite, and complete multipartite graphs while offering optimal or near-optimal solutions for any multipartite, random, and social networks. These findings emphasize the applicability and solution efficiency of the edge coloring problem in various scenarios within graph theory.

Keywords

• Edge coloring algorithm
• Minimum edge coloring
• Malatya centrality
• Matching approach

Kenar Renklendirme için Etkili bir Algoritma: Malatya Kenar Renklendirme Algoritması

Abstract

Bu çalışmada çizge teorisinde kenar renklendirme problemi için etkili ve sağlam çözümler sunan bir algoritma önerilmektedir. Kenar renklendirme problemi, çözüm süresinin uzunluğu ve polinomsal zamanda çözülememesi ile bilinen NP-zor bir problem olarak tanımlanmaktadır. Önerilen kenar renklendirme algoritması, polinomsal zaman kısıtları içinde etkili çözümler sunan verimli bir açgözlü (greedy) yöntem olarak ortaya çıkmaktadır. Geliştirilen bu algoritma, kenar renklendirme sürecinde belirleyici bir faktör olarak Malatya merkezilik (centrality) değerlerini kullanmaktadır. Güncel bir merkezilik yöntemi olan Malatya merkezilik algoritması, literatürde çeşitli çizge problemlerinde başarılı sonuçlar elde etmiştir. Bu çalışmada, algoritma Malatya Kenar Renklendirme Algoritması (MECA) olarak adlandırılmıştır. MECA’nın başarısını vurgulamak amacıyla, analitik kanıtları iyi bilinen grafikler üzerinde hesaplamalı olarak doğrulanmıştır. Ayrıca, MECA; 40 ağırlıksız ve yönsüz örgü (lattice) çizge, 36 iki parçalı (bipartite), 24 çok parçalı (multipartite), 8 rastgele ve sosyal ağ çizge üzerinde test edilmiştir. Elde edilen sonuçlar, MECA’nın örgü, iki parçalı ve tam çok parçalı çizgeler için optimal çözümler sağladığını, çok parçalı, rastgele ve sosyal ağ grafiklerinde ise optimal veya optimal’e yakın çözümler sunduğunu göstermektedir. Bu bulgular, MECA’nın çizge teorisi bağlamında çeşitli senaryolarda kenar renklendirme probleminin uygulanabilirliği ve çözüm etkinliği açısından önemli bir katkı sunduğunu vurgulamaktadır.

Keywords

• Kenar renklendirme algoritması
• minimum kenar renklendirme
• Malatya merkezlilik
• eşleştirme yaklaşımı.

References

1. Plantholt MJ, Shan S. Edge coloring graphs with large minimum degree. J Graph Theory 2023; 102: 611–632.
2. Badoni RP, Gupta DK. A graph edge colouring approach for school timetabling problems. Int J Math Oper Res 2014; 7(2): 123-138.
3. Bellitto T, Li S, Okrasa K, et al. The complexity of routing problems in forbidden-transition graphs and edge-colored graphs. Algorithmica 2023; 85: 1202–1250.
4. Yakut S, Öztemiz F, Karci A. A new approach based on centrality value in solving the maximum independent set problem: Malatya centrality algorithm. Comput Sci 2023; 8(1): 16-23.
5. Yakut S, Öztemiz F, Karci A. A new robust approach to solve minimum vertex cover problem: Malatya vertex-cover algorithm. J Supercomput 2023; 79: 19746–19769.
6. Öztemiz F. İki parçalı eşleştirme ile maksimum akış. Comput Sci 2023; 8(2): 102-109.
7. Foucaud F, Hocquard H, Lajou D. Complexity and algorithms for injective edge-coloring in graphs. Inf Process Lett 2021; 170: 106121.
8. Furmańczyk H, Kosowski A, Ries B, Żyliński P. Mixed graph edge coloring. Discrete Math 2009; 309(12): 4027-4036.

9. Basavaraju M, Chandran LS. A note on acyclic edge coloring of complete bipartite graphs. Discrete Math 2009; 309(13): 4646-4648.
10. Venkateswarlu A, Sarkar S, Ananthanarayanan SM. On acyclic edge-coloring of complete bipartite graphs. Discrete Math 2017; 340(3): 481-493.
11. Plantholt MJ, Shan S. Edge coloring graphs with large minimum degree. J Graph Theory 2023; 102: 611–632.
12. Basavaraju M, Chandran LS. Acyclic edge coloring of graphs with maximum degree 4. J Graph Theory 2009; 61: 192-209.
13. Junlei Z. Injective edge coloring of graphs with maximum degree 5. Discrete Appl Math 2023; 334: 119-126.
14. Cardoso DM, Cerdeira OJ, Dominicc C, Cruz PJ. Injective edge coloring of graphs. Filomat 2019; 33(19): 6411-6423.
15. Andersen LD, Máčajová E, Mazák J. Optimal acyclic edge-coloring of cubic graphs. J Graph Theory 2012; 71: 353-364.
16. Kano M, Li X. Monochromatic and heterochromatic subgraphs in edge-colored graphs: A survey. Graphs Combin 2008; 24: 237–263.
17. Miao Z, Song Y, Wang T, Yu X. List star edge coloring of generalized Halin graphs. Discrete Math 2023; 346(1): 113204.
18. Balister PN, Riordan OM, Schelp RH. Vertex-distinguishing edge colorings of graphs. J Graph Theory 2003; 42: 95-109.
19. Fabrício S, Benevides CH, Rudini MS. Edge-colorings of graphs avoiding complete graphs with a prescribed coloring. Discrete Math 2017; 340(9): 2143-2160.
20. Wdowinski R. Orientation-based edge-colorings and linear arboricity of multigraphs. J Graph Theory 2023; 102: 633–647.
21. Li X, Li Y, Lv JB, Wang T. Strong edge-colorings of sparse graphs with 3Δ−1 colors. Inf Process Lett 2023; 179: 106313.
22. Dey A, Son LH, Kumar PKK, Selvachandran G, Quek SG. New concepts on vertex and edge coloring of simple vague graphs. Symmetry 2018; 10(9): 373.
23. Basavaraju M, Chandran LS. Acyclic edge coloring of 2-degenerate graphs. J Graph Theory 2012; 69: 1-27.
24. Dey A, Ghosh D, Pal A. Edge coloring of a complement fuzzy graph. Int J Mod Eng Res (IJMER) 2012; 2: 1929-1933.
25. Mazzuoccolo G, Mkrtchyan V. Normal edge-colorings of cubic graphs. J Graph Theory 2020; 94: 75–91.
26. Halldórsson MM, Nolin A. Superfast coloring in CONGEST via efficient color sampling. Theor Comput Sci 2023; 948: 113711.
27. Akbari S, Beikmohammadi A, Brešar B, Dravec T, Habibollahi MM, Movarraei N. On the chromatic edge stability index of graphs. Eur J Comb 2023; 111: 103690.
28. Esperet L, Parreau A. Acyclic edge-coloring using entropy compression. Eur J Comb 2013; 34(6): 1019-1027.
29. Kostochka A, Raspaud A, Xu J. Injective edge-coloring of graphs with given maximum degree. Eur J Comb 2021; 96: 103355.
30. Januario T, Urrutia S, Ribeiro CC. Edge coloring: A natural model for sports scheduling. Eur J Oper Res 2016; 254(1): 1-8.
31. Feng W, Zhang L, Wang H. Approximation algorithm for maximum edge coloring. Theor Comput Sci 2009; 410(11): 1022-1029.
32. Ito T, Kato A, Zhou X, Nishizeki T. Algorithms for finding distance-edge-colorings of graphs. J Discrete Algorithms 2007; 5(2): 304-322.
33. Ghaffari M, Kuhn F, Maus Y, Uitto J. Deterministic distributed edge-coloring with fewer colors. In: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2018); Association for Computing Machinery; New York, NY, USA, 2018. pp. 418–430.
34. Kowalik Ł. Improved edge-coloring with three colors. Theor Comput Sci 2009; 410(38–40): 3733-3742.
35. Behnezhad S, Derakhshan M, Hajiaghayi M, Knittel M, Saleh H. Streaming and massively parallel algorithms for edge coloring. In: 27th Annual European Symposium on Algorithms (ESA 2019); Leibniz International Proceedings in Informatics (LIPIcs), 2019. pp. 15:1-15:14.
36. Lužar B, Maceková M, Rindošová S, Soták R, Sroková K, Štorgel K. Locally irregular edge-coloring of subcubic graphs. Discrete Appl Math 2023; 339: 136-148.
37. Gandham S, Dawande M, Prakash R. Link scheduling in wireless sensor networks: Distributed edge-coloring revisited. J Parallel Distrib Comput 2008; 68(8): 1122-1134.
38. Zhou X, Nishizeki T. Algorithm for the cost edge-coloring of trees. J Comb Optim 2004; 8: 97–108.
39. Akbari S, Haslegrave J, Javadi M, Nahvi N, Niaparast H. Tight bounds on the chromatic edge stability index of graphs. Discrete Math 2024; 347(4): 113850.
40. Bernshteyn A. A fast distributed algorithm for (Δ+1)-edge-coloring. J Comb Theory Ser B 2022; 152: 319-352.
41. Chen G, Hao Y. On the coequal values of total chromatic number and chromatic index. J Comb Theory Ser B 2023; 158(2): 286-304
42. Abrahamyan S. On maximum matchings in 5-regular and 6-regular multigraphs. Discrete Math 2023; 346(2): 113243.
43. Le VB, Telle JA. The perfect matching cut problem revisited. Theor Comput Sci 2022; 931: 117-130.
44. Karci A, Yakut S, Öztemiz F. A new approach based on centrality value in solving the minimum vertex cover problem: Malatya centrality algorithm. Comput Sci 2022; 7(2): 81-88.
45. Mohd-Zaid F, Kabban SC, Deckro RF, Shamp W. Network characterization and simulation via mixed properties of the Barabási–Albert and Erdös–Rényi degree distribution. J Def Model Simul 2024; 21(1): 87-102.
46. Akbari S, Alipour A. Multicolored trees in complete graphs. J Graph Theory 2007; 54: 221-232.