#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: |
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
- Status changed from new to needs_info
comment:2 Changed 9 years ago by
- 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
- Milestone changed from sage-5.0 to sage-duplicate/invalid/wontfix
Note: See
TracTickets for help on using
tickets.
Could it be the one that was fixed in #12389 ?
:-)
Nathann