Hey, I'm curious about the state of the art in solving graph coloring (by solving I mean finding the optimal coloring and proving that it is optimal). Can someone point me to papers describing solvers/implementation of solvers both for finding colorings quickly and for proving optimality which are state of the art? Thanks asked 04 Jun '10, 02:00 Sid 
I keep wanting to update the results and details at http://mat.tepper.cmu.edu/COLOR04 but just never get the time. There is a very nice survey in the January 2010 International Transactions in Operational Research by Malaguti and Toth. answered 05 Jul '10, 21:40 Michael Trick ♦♦ Just for the sake of completeness: "A survey on vertex coloring problems" /by Malaguti, Toth  in: ITOR 17:1, 134, Jan 2010 (DOI: 10.1111/j.14753995.2009.00696.x)
(06 Jul '10, 12:04)
fbahr ♦

Apart, from the bibliography web site, Marco Chiarandini and myself mantain an up to date web page with best results (lower and upper bounds) with several links to resources related to graph coloring. One of the web page is dedicated to available implementations answered 14 Sep '12, 03:06 Stefano Gual... 
Marco Chiarandini and Stefano Gualandi maintain a comprehensive (not claimed to be exhaustive, though) Bibliography on GraphVertex Coloring (last updated: June 24, 2010) answered 06 Jul '10, 12:10 fbahr ♦ 
Please see: http://users.business.uconn.edu/mdiaby/publishedP=NPpapers/vcplp.pdf. I don't think the LP model presented there can tackle practical problems directly at this time, because of its large scale. However, in principle, it always gives an optimal solution to the VCP. answered 05 Jul '10, 06:03 Moustapha Diaby 3
The paper referred to claims to show P=NP, so you might decide whether you believe that before you go down that path. See http://mat.tepper.cmu.edu/blog/?p=767 for some thoughts on P=NP research. But, to my knowledge, there is not a single instance that was previously unsolved that is solved by this LP approach. It is, at best, a theoretical result.
(06 Jul '10, 01:52)
Michael Trick ♦♦
I just love the P=NP stuff :) I have been to a few talks, where the speaker ended up claiming P=NP and I hate myself for not see it coming, avoid wasting my time..
(06 Jul '10, 06:10)
Bo Jensen ♦

See this paper: http://www.plosone.org/article/info%3Adoi%2F10.1371%2Fjournal.pone.0053437 Ant the online graph coloring application: answered 31 Jul '13, 10:57 Jose Antonio... 