most recent 30 from http://mathoverflow.net 2013-05-20T12:03:23Z http://mathoverflow.net/feeds/user/8054 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/33812/lower-bounds-for-chromatic-number-of-a-graph/33921#33921 Marco Chiarandini 2010-07-30T16:20:02Z 2010-07-30T16:20:02Z

<p>I discussed this issue with Stefano Gualandi a few days ago while setting up this page: <a href="http://sites.google.com/site/graphcoloring/vertex-coloring" rel="nofollow">http://sites.google.com/site/graphcoloring/vertex-coloring</a></p> <p>As evidenced from the results in the web page, for arbitrary graphs of large size the best lower bound is often found by the fractional chromatic number.</p> <p>This number is found by solving the linear relaxation of the integer programming formulation of the chromatic number problem. You find it, for example, here: <a href="http://www.optimization-online.org/DB_HTML/2005/12/1257.html" rel="nofollow">http://www.optimization-online.org/DB_HTML/2005/12/1257.html</a> eq. 11-13.</p> <p>Computationally, you have to find a collection of maximal stable sets that covers all vertices (some may be included more than once), and then solve the corresponding LP relaxation of the chromatic number problem. The computational burden lays in the fact that the collection contains an exponential number of elements. The fractional chromatic number problem is also NP-hard.</p> <p>However, there are techniques that can avoid generating all maximal stable sets. See for example: <a href="http://www.optimization-online.org/DB_HTML/2010/03/2568.html" rel="nofollow">http://www.optimization-online.org/DB_HTML/2010/03/2568.html</a> Alternatively, some stable sets chosen heuristically can be used but the result of the LP will not be the fractional chromatic number in this case. </p> <p>If you need computational results and cannot find a way to obtain them yourself you can write to Stefano (who has all programs). </p>

http://mathoverflow.net/questions/33812/lower-bounds-for-chromatic-number-of-a-graph/33921#33921 Marco Chiarandini 2010-08-01T16:25:56Z 2010-08-01T16:25:56Z

In this article, table 4, <a href="http://www.optimization-online.org/DB_HTML/2010/03/2568.html" rel="nofollow">optimization-online.org/DB_HTML/2010/03/2568.html</a> there are results for a time bound of 3600 seconds. Whether the fractional chromatic number problem for a graph of 560 vertices can be solved within this time bound depends on the type of graph. From the table it seems that denser graphs are more likely to be solved earlier.