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."
From "The Mutually Beneficial Relationship of Graphs and Matrices", Richard
A. Brualdi,CBMS Series,Number 115, 2011.
On Fri, Jul 13, 2012 at 1:43 PM, Alec Story <avs38@corn...> wrote:
> I have a problem where I need to find the smallest k-coloring for a graph
> that represents conflicts between objects. Is there a Haskell library that
> will do this for me? I'm not particularly concerned about speed, and it's
> unlikely that I'll generate really bad edge cases, but I'd prefer to do
> something other than write the really bad try-every-case algorithm.
> Alec Story
> Cornell University
> Biological Sciences, Computer Science 2012
> Beginners mailing list
> Beginners@hask... > http://www.haskell.org/mailman/listinfo/beginners >