Ask Your Question

optimizing graph coloring for small chromatic number

asked 2015-01-04 14:35:41 -0500

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?

edit retag flag offensive close merge delete



Have you looked at the doc of chromatic_number ? It explains that it is best to install a MILP solver and then use algorithm="MILP".

FrédéricC gravatar imageFrédéricC ( 2015-01-04 14:55:37 -0500 )edit

1 answer

Sort by » oldest newest most voted

answered 2015-01-04 22:01:48 -0500

I just found that there is another Sage command, called vertex_coloring, which will check whether a graph is k-colorable for any particular k. You can also specify LP solver.

edit flag offensive delete link more



And in this special case installing cplex or gurobi should result in MUCH faster computation. See bottom of

Nathann gravatar imageNathann ( 2015-01-05 06:01:59 -0500 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools


Asked: 2015-01-04 14:35:41 -0500

Seen: 315 times

Last updated: Jan 04 '15