An Approach for Graph Coloring Problem Using Grouping of Vertices

Publications

An Approach for Graph Coloring Problem Using Grouping of Vertices

Year : 2022

Publisher : Springer Science and Business Media Deutschland GmbH

Source Title : Lecture Notes in Networks and Systems

Document Type :

Abstract

The algorithm works by dividing the nodes of a graph G into two groups; one is non-visited type of groups including the nodes that are not colored and visited type of groups including the nodes that are already colored and hence finds minimum number of colors that have been filled into visited nodes. An assumption is taken that k number of colors is already given, and the colors are selected from the same k colors. The proposed algorithm is implemented on random graphs along with some well-known graph coloring DIMACS benchmarks. In this research paper, an efficient graph color algorithm is proposed that uses a reduced number of colors for the well-known graph coloring problem. This projected algorithm can be applied to all types of graphs.