No subject

A. Brualdi,CBMS Series,Number 115, 2011.



On Fri, Jul 13, 2012 at 1:43 PM, Alec Story <avs38 at 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
> Beginners at haskell.org
> http://www.haskell.org/mailman/listinfo/beginners
>
>


-- 
--
Regards,
KC

--20cf300facd79c8f0904c4d143c7
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

This may help:<div>- use hMatrix to find the eigenvalues of the adjacency m=
atrix</div><div><br></div><div>Then by the following theorems:</div><div><b=
r></div><div>&quot;An upper bound on the chromatic number in terms of eigen=
values was discovered by Wilf(1967).</div>
<div><br></div><div>Chromatic Number(G) &lt;=3D 1 + lambda_1(G)</div><div><=
br></div><div>Hoffman (1977) discovered a lower bound on the chromatic numb=
er in terms of the smallest and largest eigenvalue.</div><div><br></div><di=
v>
Chromatic Number(G)=A0=A0&gt;=3D 1 - (lambda_1/lambda_n) for n&gt;=3D2.&quo=
t;</div><div><br></div><div>From &quot;The Mutually Beneficial Relationship=
 of Graphs and Matrices&quot;, Richard A. Brualdi,CBMS Series,Number 115, 2=
011.</div>
<div><br></div><div><br><br><div class=3D"gmail_quote">On Fri, Jul 13, 2012=
 at 1:43 PM, Alec Story <span dir=3D"ltr">&lt;<a href=3D"mailto:avs38 at corne=
ll.edu" target=3D"_blank">avs38 at cornell.edu</a>&gt;</span> wrote:<br><block=
quote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc=
 solid;padding-left:1ex">
I have a problem where I need to find the smallest k-coloring for a graph t=
hat represents conflicts between objects.=A0 Is there a Haskell library tha=
t will do this for me?=A0 I&#39;m not particularly concerned about speed, a=
nd it&#39;s unlikely that I&#39;ll generate really bad edge cases, but I&#3=
9;d prefer to do something other than write the really bad try-every-case a=
lgorithm.<span class=3D"HOEnZb"><font color=3D"#888888"><br clear=3D"all">


<br>-- <br>Alec Story<br>Cornell University<br>Biological Sciences, Compute=
r Science 2012<br>
</font></span><br>_______________________________________________<br>
Beginners mailing list<br>
<a href=3D"mailto:Beginners at haskell.org">Beginners at haskell.org</a><br>
<a href=3D"http://www.haskell.org/mailman/listinfo/beginners" target=3D"_bl=
ank">http://www.haskell.org/mailman/listinfo/beginners</a><br>
<br></blockquote></div><br><br clear=3D"all"><div><br></div>-- <br>--<br>Re=
gards,<br>KC<br>
</div>

--20cf300facd79c8f0904c4d143c7--