Revision history [back]

Using the double question mark to see the source code (vertex_coloring??) I see that it loops over increasingly large values of k, testing whether the graph is k-colorable:

    while True:
        # tries to color the graph, increasing k each time it fails.
        tmp = vertex_coloring(g, k=k, value_only=value_only,
                              hex_colors=hex_colors, verbose=verbose)
        if tmp is not False:
            if value_only:
                return k
            else:
                return tmp
        k += 1

So one simple idea is to do this loop manually. If the process quits, at least you'll know what values of k have already been checked:

sage: from sage.graphs.graph_coloring import vertex_coloring
sage: from sys import stdout
sage: g = graphs.CompleteGraph(9)
sage: for k in range(15):
    print '%s-colorable: %s'%(k,vertex_coloring(g, k=k, value_only=True))
    stdout.flush()
....:     
0-colorable: False
1-colorable: False
2-colorable: False
3-colorable: False
4-colorable: False
5-colorable: False
6-colorable: False
7-colorable: False
8-colorable: False
9-colorable: True
10-colorable: True
11-colorable: True
12-colorable: True
13-colorable: True
14-colorable: True