Efficient and Robust Graph Coloring Algorithm for Graph Coloring Problem: Malatya Vertex Coloring Algorithm

Basit Öğe Kaydı
dc.contributor.authorYakut, Selman
dc.date.accessioned2026-04-04T13:33:24Z
dc.date.available2026-04-04T13:33:24Z
dc.date.issued2025
dc.departmentİnönü Üniversitesi
dc.description.abstractThe graph coloring problem involves coloring the nodes of a graph using the minimum number of colors such that no two adjacent nodes share the same color. This NP-hard problem has various real-world applications, including scheduling problems, map coloring, and resource allocation. Although numerous algorithms have been proposed in the literature to solve this problem, there is a lack of effective and robust algorithms that perform well across different types of graphs. In this study, we propose the Malatya Vertex Coloring Algorithm, an efficient and robust solution for the graph coloring problem. The proposed algorithm calculates the Malatya centrality value for each node by summing the ratios of the node's degree to the degrees of its neighboring nodes. Starting from the node with the highest Malatya centrality value, the graph is colored such that each node is assigned a color different from its neighbors. The effectiveness of the proposed algorithm is demonstrated through extensive testing and analysis. First, experiments were conducted on benchmark graphs from the literature, varying in size and complexity based on the number of nodes and edges. Additionally, tests were performed on social network graphs (which model social connections and behaviors) as well as randomly generated graphs with different densities and sizes. The results show that the proposed algorithm outperforms well-known existing methods such as Welsh-Powell, Greedy Coloring, DSatur, and RLF in terms of efficiency, robustness, and success rate. Moreover, in some graph types, it yields better results than MSISCA, another efficient and robust algorithm. It is mathematically proven that the proposed algorithm provides a solution in polynomial time for any arbitrary graph and guarantees an optimal solution for specific graph classes. The analyses and experimental results demonstrate that the Malatya Vertex Coloring Algorithm delivers effective and robust solutions for the graph coloring problem across various graph types without any constraints or parameter dependencies.
dc.description.sponsorshipIdot;nonu University Scientific Research Projects Unit [FBA-2025-4086]
dc.description.sponsorshipThis work was supported by the & Idot;nonu University Scientific Research Projects Unit under Project FBA-2025-4086.
dc.identifier.doi10.1109/ACCESS.2025.3614296
dc.identifier.endpage168526
dc.identifier.issn2169-3536
dc.identifier.orcid0000-0002-0649-1993
dc.identifier.scopus2-s2.0-105017750351
dc.identifier.scopusqualityQ1
dc.identifier.startpage168512
dc.identifier.urihttps://doi.org/10.1109/ACCESS.2025.3614296
dc.identifier.urihttps://hdl.handle.net/11616/109134
dc.identifier.volume13
dc.identifier.wosWOS:001586205100014
dc.identifier.wosqualityQ2
dc.indekslendigikaynakWeb of Science
dc.indekslendigikaynakScopus
dc.institutionauthorYakut, Selman
dc.language.isoen
dc.publisherIeee-Inst Electrical Electronics Engineers Inc
dc.relation.ispartofIEEE Access
dc.relation.publicationcategoryMakale - Uluslararası Hakemli Dergi - Kurum Öğretim Elemanı
dc.rightsinfo:eu-repo/semantics/openAccess
dc.snmzKA_WOS_20250329
dc.subjectColor
dc.subjectBenchmark testing
dc.subjectHeuristic algorithms
dc.subjectClassification algorithms
dc.subjectImage color analysis
dc.subjectResource management
dc.subjectNP-hard problem
dc.subjectMachine learning algorithms
dc.subjectGraph theory
dc.subjectSocial networking (online)
dc.subjectGraph coloring problem
dc.subjectgraph theory
dc.subjectMalatya centrality algorithm
dc.subjectMalatya vertex coloring algorithm
dc.titleEfficient and Robust Graph Coloring Algorithm for Graph Coloring Problem: Malatya Vertex Coloring Algorithm
dc.typeArticle

Dosyalar

Koleksiyon

WoS İndeksli Yayınlar Koleksiyonu
Scopus İndeksli Yayınlar Koleksiyonu