Graph Coloring Using Eigenvalue Decomposition

Abstract

Determining whether the vertices of a graph can be colored using $k$ different colors so that no two adjacent vertices receive the same color is a well-known NP-complete problem. Graph coloring is also of practical interest (for example, in estimating sparse Jacobians and in scheduling), and many heuristic algorithms have been developed. We present a heuristic algorithm based on the eigenvalue decomposition of the adjacency matrix of a graph. Eigenvectors point out "bipartite-looking" subgraphs that are used to refine the coloring to a valid coloring. The algorithm optimally colors complete $k$-partite graphs and certain other classes of graphs with regular structure.