ASKSAGE: Sage Q&A Forum - Individual question feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Mon, 05 Jan 2015 06:01:59 -0600optimizing graph coloring for small chromatic numberhttps://ask.sagemath.org/question/25395/optimizing-graph-coloring-for-small-chromatic-number/I am using Sage to compute chromatic number of some moderately large graphs G (a few thousand vertices). These graphs are relatively sparse (average degree < 15) and the chromatic number is fairly small–––the graphs I've been looking at tend to have chromatic number either 4 or 5. For my purposes, though, there is a big difference between 4 and 5.
––I've been using G.chromatic_number() as a black box, but is there some way I could just ask Sage directly if the graph is 4-colorable? (If the answer is 'no' maybe I don't care about whether the chromatic number is actually 5, 6, or larger.)
––Also, is there anything else I can do to optimize chromatic number calculations in Sage if I know a priori that the chromatic number is relatively small?
Sun, 04 Jan 2015 14:35:41 -0600https://ask.sagemath.org/question/25395/optimizing-graph-coloring-for-small-chromatic-number/Comment by FrédéricC for <p>I am using Sage to compute chromatic number of some moderately large graphs G (a few thousand vertices). These graphs are relatively sparse (average degree < 15) and the chromatic number is fairly small–––the graphs I've been looking at tend to have chromatic number either 4 or 5. For my purposes, though, there is a big difference between 4 and 5.</p>
<p>––I've been using G.chromatic_number() as a black box, but is there some way I could just ask Sage directly if the graph is 4-colorable? (If the answer is 'no' maybe I don't care about whether the chromatic number is actually 5, 6, or larger.)</p>
<p>––Also, is there anything else I can do to optimize chromatic number calculations in Sage if I know a priori that the chromatic number is relatively small?</p>
https://ask.sagemath.org/question/25395/optimizing-graph-coloring-for-small-chromatic-number/?comment=25396#post-id-25396Have you looked at the doc of `chromatic_number` ? It explains that it is best to install a MILP solver and then use `algorithm="MILP"`.Sun, 04 Jan 2015 14:55:37 -0600https://ask.sagemath.org/question/25395/optimizing-graph-coloring-for-small-chromatic-number/?comment=25396#post-id-25396Answer by MattKahle for <p>I am using Sage to compute chromatic number of some moderately large graphs G (a few thousand vertices). These graphs are relatively sparse (average degree < 15) and the chromatic number is fairly small–––the graphs I've been looking at tend to have chromatic number either 4 or 5. For my purposes, though, there is a big difference between 4 and 5.</p>
<p>––I've been using G.chromatic_number() as a black box, but is there some way I could just ask Sage directly if the graph is 4-colorable? (If the answer is 'no' maybe I don't care about whether the chromatic number is actually 5, 6, or larger.)</p>
<p>––Also, is there anything else I can do to optimize chromatic number calculations in Sage if I know a priori that the chromatic number is relatively small?</p>
https://ask.sagemath.org/question/25395/optimizing-graph-coloring-for-small-chromatic-number/?answer=25398#post-id-25398I just found that there is another Sage command, called [vertex_coloring](http://www.sagemath.org/doc/reference/graphs/sage/graphs/graph_coloring.html#sage.graphs.graph_coloring.vertex_coloring), which will check whether a graph is k-colorable for any particular k. You can also specify LP solver.
Sun, 04 Jan 2015 22:01:48 -0600https://ask.sagemath.org/question/25395/optimizing-graph-coloring-for-small-chromatic-number/?answer=25398#post-id-25398Comment by Nathann for <p>I just found that there is another Sage command, called <a href="http://www.sagemath.org/doc/reference/graphs/sage/graphs/graph_coloring.html#sage.graphs.graph_coloring.vertex_coloring">vertex_coloring</a>, which will check whether a graph is k-colorable for any particular k. You can also specify LP solver.</p>
https://ask.sagemath.org/question/25395/optimizing-graph-coloring-for-small-chromatic-number/?comment=25400#post-id-25400And in this special case installing cplex or gurobi should result in MUCH faster computation. See bottom of http://www.sagemath.org/doc/thematic_tutorials/linear_programming.htmlMon, 05 Jan 2015 06:01:59 -0600https://ask.sagemath.org/question/25395/optimizing-graph-coloring-for-small-chromatic-number/?comment=25400#post-id-25400