A robust and efficient algorithm for graph coloring problem based on Malatya centrality and sequent independent sets

Basit Öğe Kaydı
dc.contributor.authorYakut, Selman
dc.date.accessioned2026-04-04T13:35:09Z
dc.date.available2026-04-04T13:35:09Z
dc.date.issued2025
dc.departmentİnönü Üniversitesi
dc.description.abstractThe Graph Coloring Problem (GCP) is an NP-hard problem that aims to color the vertices of a graph using the minimum number of distinct colors, ensuring that adjacent vertices do not share the same color. GCP is widely applied in real-world scenarios and graph theory problems. Despite numerous studies on solving GCP, existing methods face limitations, often performing well on specific graph types but failing to deliver efficient solutions across diverse structures. This study introduces the Malatya Sequent Independent Set Coloring Algorithm as an effective solution for GCP. The algorithm utilizes the Malatya Centrality Algorithm to compute Malatya Centrality (MC) values for graph vertices, where an MC value is defined as the sum of the ratios of a vertex's degree to its neighbors' degrees. The algorithm selects the vertex with the lowest MC value, adds it to an independent set, and removes it along with its neighbors and edges. This process repeats until the first sequent independent set is identified. The removed set is then excluded from the original graph, and the process continues on the remaining structure to determine additional sequent independent sets, ensuring that each set corresponds to a single color group in GCP. The algorithm was tested on social network graphs, random graphs, and benchmark datasets, supported by mathematical analyses and proofs. The results confirm that the algorithm provides efficient, polynomial-time solutions for GCP and maintains high performance across various graph types, independent of constraints.
dc.identifier.doi10.1016/j.eij.2025.100676
dc.identifier.issn1110-8665
dc.identifier.issn2090-4754
dc.identifier.orcid0000-0002-0649-1993
dc.identifier.scopus2-s2.0-105002241912
dc.identifier.scopusqualityQ1
dc.identifier.urihttps://doi.org/10.1016/j.eij.2025.100676
dc.identifier.urihttps://hdl.handle.net/11616/109650
dc.identifier.volume30
dc.identifier.wosWOS:001483976000001
dc.identifier.wosqualityQ2
dc.indekslendigikaynakWeb of Science
dc.indekslendigikaynakScopus
dc.institutionauthorYakut, Selman
dc.language.isoen
dc.publisherCairo Univ, Fac Computers & Information
dc.relation.ispartofEgyptian Informatics Journal
dc.relation.publicationcategoryMakale - Uluslararası Hakemli Dergi - Kurum Öğretim Elemanı
dc.rightsinfo:eu-repo/semantics/openAccess
dc.snmzKA_WOS_20250329
dc.subjectGraph coloring problem
dc.subjectChromatic numbers
dc.subjectMalatya centrality algorithm
dc.subjectMalatya sequent independent set coloring
dc.subjectalgorithm
dc.subjectIndependent sets
dc.titleA robust and efficient algorithm for graph coloring problem based on Malatya centrality and sequent independent sets
dc.typeArticle

Dosyalar

Koleksiyon

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