An Effective Algorithm for Edge Coloring: Malatya Edge Coloring Algorithm
Furkan Öztemız · Turkish Journal of Science and Technology · 2025
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.