[Haskell-cafe] [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 Haskell-Cafe
mailing list