[Haskell-beginners] Graph Coloring Library?

KC kc1956 at gmail.com
Sat Jul 14 23:56:08 CEST 2012


This may help:
- use hMatrix to find the eigenvalues of the adjacency matrix

Then by the following theorems:

"An upper bound on the chromatic number in terms of eigenvalues was
discovered by Wilf(1967).

Chromatic Number(G) <= 1 + lambda_1(G)

Hoffman (1977) discovered a lower bound on the chromatic number in terms of
the smallest and largest eigenvalue.

Chromatic Number(G)  >= 1 - (lambda_1/lambda_n) for n>=2."



More information about the Beginners mailing list