Ask Your Question
1

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

Comments

1

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
1

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

Comments

2

And in this special case installing cplex or gurobi should result in MUCH faster computation. See bottom of http://www.sagemath.org/doc/thematic_...

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

Stats

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

Seen: 349 times

Last updated: Jan 04 '15