Graph Coloring Using Eigenvalue Decomposition

Authors:
  • BABengt Aspvall
    Bengt Aspvall
  • JGJohn R. Gilbert
    John R. Gilbert
  • BGBengt Aspvall And John R. Gilbert
    Bengt Aspvall And John R. Gilbert
  • JAJonathan E. Atkins
    Jonathan E. Atkins
  • EBErik G. Boman
    Erik G. Boman
  • BHBruce Hendrickson
    Bruce Hendrickson
  • NANoga Alon
    Noga Alon
  • NKNabil Kahale
    Nabil Kahale

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.

This publication has 17 references indexed in Scilit: