Opened 9 years ago

Closed 9 years ago

Last modified 9 years ago

#12485 closed defect (duplicate)

bug in chromatic number

Reported by: was Owned by: jason, ncohen, rlm
Priority: minor Milestone: sage-duplicate/invalid/wontfix
Component: graph theory Keywords:
Cc: ncohen Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description

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.

Change History (3)

comment:1 Changed 9 years ago by ncohen

  • Status changed from new to needs_info

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

Nathann

comment:2 Changed 9 years ago by was

  • Resolution set to duplicate
  • Status changed from needs_info to closed

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

comment:3 Changed 9 years ago by mvngu

  • Milestone changed from sage-5.0 to sage-duplicate/invalid/wontfix
Note: See TracTickets for help on using tickets.