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?


asked 04 Jun '10, 02:00

Sid's gravatar image

accept rate: 18%

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%20Trick's gravatar image

Michael Trick ♦♦
accept rate: 20%

Just for the sake of completeness: "A survey on vertex coloring problems" /by Malaguti, Toth - in: ITOR 17:1, 1-34, Jan 2010 (DOI: 10.1111/j.1475-3995.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%20Gualandi's gravatar image

Stefano Gual...
accept rate: 0%

edited 14 Sep '12, 03:16

Marco Chiarandini and Stefano Gualandi maintain a comprehensive (not claimed to be exhaustive, though) Bibliography on Graph-Vertex Coloring (last updated: June 24, 2010)


answered 06 Jul '10, 12:10

fbahr's gravatar image

fbahr ♦
accept rate: 13%

edited 14 Sep '12, 04:22

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%20Diaby's gravatar image

Moustapha Diaby
accept rate: 0%


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 ♦

I just read Diaby's paper at link text

The wrong part is its theorem 1; It implies (wrongly) that all extreme point of the polytope are integral. No proof is given of the theorem, other than "Trivial".

(11 Sep '12, 23:20) jfpuget

answered 31 Jul '13, 10:57

Jose%20Antonio%20Martin%20H's gravatar image

Jose Antonio...
accept rate: 0%

Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported



Asked: 04 Jun '10, 02:00

Seen: 5,805 times

Last updated: 31 Jul '13, 10:57

OR-Exchange! Your site for questions, answers, and announcements about operations research.