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 <av...@cornell.edu> 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 > beginn...@haskell.org > http://www.haskell.org/mailman/listinfo/beginners > > -- -- Regards, KC
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
