bug in chromatic number

[williamstein]

This triggers a bug:

sage: g = graphs.IcosahedralGraph()
sage: g.chromatic_number(algorithm='MILP')

The bug is in graphs/graph_coloring.py. In particular, this code is bogus:

        # - No need to try any k smaller than the maximum clique in
        # - the graph No need to try k less than |G|/alpha(G), as each
        #   color class is at most alpha(G)
        # - max, because we know it is not bipartite
        from math import ceil
        k = max([3, g.clique_number(),ceil(g.order()/len(g.independent_set()))])

Somebody (see #9618) thinks that ceil returns an int, but it returns a float. Oops.

CC: @nathanncohen

Component: graph theory

Issue created by migration from https://trac.sagemath.org/ticket/12485

[nathanncohen]

comment:1

Could it be the one that was fixed in #12389 ? :-)

Nathann

[williamstein]

comment:2

Yep, that is one way to fix it. I couldn't find that searching. Oops. I'm closing this as a duplicate.