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?
Have you looked at the doc of
chromatic_number? It explains that it is best to install a MILP solver and then usealgorithm="MILP".