Ask Your Question
1

optimizing graph coloring for small chromatic number

asked 2015-01-04 21:35:41 +0200

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 21:55:37 +0200 )edit

1 Answer

Sort by » oldest newest most voted
1

answered 2015-01-05 05:01:48 +0200

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 13:01:59 +0200 )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 21:35:41 +0200

Seen: 630 times

Last updated: Jan 05 '15