Coloring a graph involves labeling each node so that adjacent nodes have different labels. A minimum coloring of a graph is a coloring that uses as few different labels as possible. The problem of coloring graph with the minimum number of colors is well known to be NP-Hard. In this paper, a new clustering based algorithm is presented for the graph coloring problem with the minimum number of colors. The proposed algorithm is evaluated on the DIMACS challenge benchmarks. We compare the results with three other existing coloring algorithms and experimental results on DIMACS graphs Benchmark instances show improvements over existing algorithms for the graph coloring problem.
展开▼
