Revision history [back]

Minor improvement to chromatic number

If any one wants to, here is a very minor change you could make in the calculation of chromatic number that would make it faster! The change is to take the line that says

if len(G.edges()) == 0:

if G.size() == 0:

def chromatic_number(G):
    r"""
    Returns the minimal number of colors needed to color the
    vertices of the graph `G`.

    EXAMPLES::

        sage: from sage.graphs.graph_coloring import chromatic_number
        sage: G = Graph({0:[1,2,3],1:[2]})
        sage: chromatic_number(G)
        3

        sage: G = graphs.PetersenGraph()
        sage: G.chromatic_number()
        3
    """
    o = G.order()
    if o == 0:
        return 0
    if len(G.edges()) == 0:
        return 1
    elif G.is_bipartite(): #can we do it in linear time?
        return 2
    else: #counting cliques is faster than our brute-force method...
        m = G.clique_number()
    if m >= o-1: #marginal improvement... if there's an o-1 clique and not an o clique, don't waste our time coloring.
        return m
    for n in range(m,o+1):
        for C in all_graph_colorings(G,n):
            return n

Minor improvement to chromatic number

If any one wants to, here is a very minor change you could make in the calculation of chromatic number that would make it faster! The change is to take the line that says

if len(G.edges()) == 0:

if G.size() == 0:

def chromatic_number(G):
    r"""
    Returns the minimal number of colors needed to color the
    vertices of the graph `G`.

    EXAMPLES::

        sage: from sage.graphs.graph_coloring import chromatic_number
        sage: G = Graph({0:[1,2,3],1:[2]})
        sage: chromatic_number(G)
        3

        sage: G = graphs.PetersenGraph()
        sage: G.chromatic_number()
        3
    """
    o = G.order()
    if o == 0:
        return 0
    if len(G.edges()) == 0:
        return 1
    elif G.is_bipartite(): #can we do it in linear time?
        return 2
    else: #counting cliques is faster than our brute-force method...
        m = G.clique_number()
    if m >= o-1: #marginal improvement... if there's an o-1 clique and not an o clique, don't waste our time coloring.
        return m
    for n in range(m,o+1):
        for C in all_graph_colorings(G,n):
            return n

Update: Nathann has already implemented this help so thanks! I thought I would give a quick update just on the timing since kcrisman asked. In fact, g.size() is much faster than len(g.edges), relatively, though the magnitudes are so small that it probably doesn't affect the chromatic number much. However, if you wanted to find the chromatic number on all graphs of order 11, over 1 billion, which I did recently, if the average time savings is 70 microseconds, that's a total savings of 70000 seconds, which is nearly 20 hours. And, since Nathann also made a similar change on all_graph_colorings, which is used in chromatic_number, the savings could be in the neighborhood of 40 hours. By the way, the time savings from len(g.vertices()) to g.order() is 8 microseconds on the graph I randomly generated.

g=graphs.RandomGNP(11,0.6)

Start with random graph of order 11

timeit('len(g.edges())')

625 loops, best of 3: 72.9 µs per loop

timeit('g.size()')

625 loops, best of 3: 1.12 µs per loop