mwang (04/05/83)
DEPARTMENT OF COMPUTER SCIENCE
UNIVERSITY OF WATERLOO
SEMINAR ACTIVITIES
THEORY SEMINAR
- Thursday, April 14, 1983.
Dr. B. Aspvall of Cornell University will speak on
``Graph Coloring Using Eigenvalue Decomposition''.
TIME: 3.30 PM
ROOM: MC 5158
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 algo-
rithms 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 cer-
tain other classes of graphs with regular structure.
Using perturbation arguments, we argue that the algo-
rithm colors a wide range of graphs well.
April 5, 1983