Opened 10 years ago

Closed 10 years ago

# Rounding error in graph coloring

Reported by: Owned by: ncohen jason, ncohen, rlm major sage-5.0 graph theory sage-5.0.beta3 Nathann Cohen David Coudert N/A

### Description

Geoff Tims reported the following bug :

```sage: sub = graphs.PetersenGraph()
sage: sub.complement().chromatic_number(algorithm="MILP")
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)

/home/ncohen/<ipython console> in <module>()

/home/ncohen/.Sage/local/lib/python2.7/site-packages/sage/graphs/graph.pyc in chromatic_number(self, algorithm)
2487         elif algorithm == "MILP":
2488             from sage.graphs.graph_coloring import vertex_coloring
-> 2489             return vertex_coloring(self, value_only=True)
2490         # another algorithm with bad performance; only good for small graphs
2491         elif algorithm == "CP":

/home/ncohen/.Sage/local/lib/python2.7/site-packages/sage/graphs/graph_coloring.pyc in vertex_coloring(g, k, value_only, hex_colors, solver, verbose)
342             # tries to color the graph, increasing k each time it fails.
343             tmp = vertex_coloring(g, k=k, value_only=value_only,
--> 344                                   hex_colors=hex_colors, verbose=verbose)
345             if tmp is not False:
346                 if value_only:

/home/ncohen/.Sage/local/lib/python2.7/site-packages/sage/graphs/graph_coloring.pyc in vertex_coloring(g, k, value_only, hex_colors, solver, verbose)
431         # a vertex has exactly one color
432         [p.add_constraint(Sum([color[v][i] for i in xrange(k)]), min=1, max=1)
--> 433              for v in g.vertices()]
434         # adjacent vertices have different colors

TypeError: integer argument expected, got float
```

### comment:1 Changed 10 years ago by ncohen

• Status changed from new to needs_review
• Summary changed from Bug in graph coloring to Rounding error in graph coloring

Here is the one-line patch needed !

Nathann

### comment:2 Changed 10 years ago by dcoudert

• Reviewers set to David Coudert
• Status changed from needs_review to positive_review

Without the patch, I observe the same error than the reported one.

With the patch:

```sage: sub = graphs.PetersenGraph()
sage: sub.complement().chromatic_number(algorithm="MILP")
5
```

So I give a positive review.

D.

### comment:3 Changed 10 years ago by jdemeyer

• Merged in set to sage-5.0.beta3
• Resolution set to fixed
• Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.