TY - JOUR
ID - 114365
TI - Solving Graph Coloring Problem Using Graph Adjacency Matrix Algorithm
JO - Mathematics Interdisciplinary Research
JA - MIR
LA - en
SN - 2538-3639
AU - Mousavi, Hanife
AU - Tavakoli, Mostafa
AU - Ghorbani-Moghadam, Khatere
AD - Department of Applied Mathematics, Faculty of Mathematical Sciences,
Ferdowsi University of Mashhad,
P.O. Box 1159, Mashhad 91775, I. R. Iran
AD - Mosaheb Institute of Mathematics,
Kharazmi University, Tehran, I. R. Iran
Y1 - 2024
PY - 2024
VL - 9
IS - 2
SP - 215
EP - 236
KW - Chromatic number
KW - Coloring number
KW - Graph coloring algorithms
KW - Graph adjacency matrix
KW - Degree of vertex
DO - 10.22052/mir.2023.253223.1428
N2 - Graph coloring is the assignment of one color to each vertex of a graph so that two adjacent vertices are not of the same color. The graph coloring problem (GCP) is a matter of combinatorial optimization, and the goal of GCP is determining the chromatic number $\chi(G)$. Since GCP is an NP-hard problem, then in this paper, we propose a new approximated algorithm for finding the coloring number (it is an approximation of chromatic number) by using a graph adjacency matrix to colorize or separate a graph. To prove the correctness of the proposed algorithm, we implement it in MATLAB software, and for analysis in terms of solution and execution time, we compare our algorithm with some of the best existing algorithms that are already implemented in MATLAB software, and we present the results in tables of various graphs. Several available algorithms used the largest degree selection strategy, while our proposed algorithm uses the graph adjacency matrix to select the vertex that has the smallest degree for coloring. We provide some examples to compare the performance of our algorithm to other available methods. We make use of the Dolan-Mor\'e performance profiles to assess the performance of the numerical algorithms, and demonstrate the efficiency of our proposed approach in comparison with some existing methods.
UR - https://mir.kashanu.ac.ir/article_114365.html
L1 - https://mir.kashanu.ac.ir/article_114365_c868980d403a0fffefea025c5535ae23.pdf
ER -