A robust and efficient algorithm for graph coloring problem based on Malatya centrality and sequent independent sets
The 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 studie...
Saved in:
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Elsevier
2025-06-01
|
| Series: | Egyptian Informatics Journal |
| Subjects: | |
| Online Access: | http://www.sciencedirect.com/science/article/pii/S1110866525000696 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850203375011889152 |
|---|---|
| author | Selman Yakut |
| author_facet | Selman Yakut |
| author_sort | Selman Yakut |
| collection | DOAJ |
| description | The 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. |
| format | Article |
| id | doaj-art-354338d73b3e4cdba2788d9c131b6191 |
| institution | OA Journals |
| issn | 1110-8665 |
| language | English |
| publishDate | 2025-06-01 |
| publisher | Elsevier |
| record_format | Article |
| series | Egyptian Informatics Journal |
| spelling | doaj-art-354338d73b3e4cdba2788d9c131b61912025-08-20T02:11:33ZengElsevierEgyptian Informatics Journal1110-86652025-06-013010067610.1016/j.eij.2025.100676A robust and efficient algorithm for graph coloring problem based on Malatya centrality and sequent independent setsSelman Yakut0Software Engineering Department, Faculty of Engineering, Inonu University, Malatya 44000, TurkeyThe 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.http://www.sciencedirect.com/science/article/pii/S1110866525000696Graph coloring problemChromatic numbersMalatya centrality algorithmMalatya sequent independent set coloring algorithmIndependent sets |
| spellingShingle | Selman Yakut A robust and efficient algorithm for graph coloring problem based on Malatya centrality and sequent independent sets Egyptian Informatics Journal Graph coloring problem Chromatic numbers Malatya centrality algorithm Malatya sequent independent set coloring algorithm Independent sets |
| title | A robust and efficient algorithm for graph coloring problem based on Malatya centrality and sequent independent sets |
| title_full | A robust and efficient algorithm for graph coloring problem based on Malatya centrality and sequent independent sets |
| title_fullStr | A robust and efficient algorithm for graph coloring problem based on Malatya centrality and sequent independent sets |
| title_full_unstemmed | A robust and efficient algorithm for graph coloring problem based on Malatya centrality and sequent independent sets |
| title_short | A robust and efficient algorithm for graph coloring problem based on Malatya centrality and sequent independent sets |
| title_sort | robust and efficient algorithm for graph coloring problem based on malatya centrality and sequent independent sets |
| topic | Graph coloring problem Chromatic numbers Malatya centrality algorithm Malatya sequent independent set coloring algorithm Independent sets |
| url | http://www.sciencedirect.com/science/article/pii/S1110866525000696 |
| work_keys_str_mv | AT selmanyakut arobustandefficientalgorithmforgraphcoloringproblembasedonmalatyacentralityandsequentindependentsets AT selmanyakut robustandefficientalgorithmforgraphcoloringproblembasedonmalatyacentralityandsequentindependentsets |