Solving Graph Coloring Problem Using Graph Adjacency Matrix Algorithm

Abstract

‎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‎.

Keywords

• chromatic number‎
• ‎coloring number‎
• ‎graph coloring algorithms‎
• ‎graph adjacency matrix‎
• ‎degree of vertex