id	summary	reporter	owner	description	type	status	priority	milestone	component	resolution	keywords	cc	work_issues	upstream	reviewer	author	merged	dependencies	stopgaps
9618	Slight improvement to vertex_coloring	ncohen	jason, ncohen, rlm	"We know that the chromatic number of a graph is more than its number of vertices divided by te size of its maximum independent set.

Sage did not.

Computations of max clique/independent set are way faster than coloring thanks to Cliquer, by the way !

The different is especially remarquable on random graphs :

After :
{{{
 sage: g = graphs.RandomGNP(40,.3)
 sage: g.graph6_string()
'geAp`wP`?pwiEc_g{M?Smecc`CIB?OCAcGAa`QO?Q?GgH?CRWQ@_?QOJwG@?????AFDGRO{FU_KGDQLACp`LOHcPCAFHBMJwRB]OMRKSAOSx_`PI_OgRBB?UBTG@IAQPBQO'
 sage: %timeit g.coloring(algorithm = ""MILP"")
 5 loops, best of 3: 241 ms per loop
}}}

Before :
{{{
 sage: g = Graph('geAp`wP`?pwiEc_g{M?Smecc`CIB?OCAcGAa`QO?Q?GgH?CRWQ@_?QOJwG@?????AFDGRO{FU_KGDQLACp`LOHcPCAFHBMJwRB]OMRKSAOSx_`PI_OgRBB?UBTG@IAQPBQO')
 sage: %timeit g.coloring(algorithm = ""MILP"")
5 loops, best of 3: 361 ms per loop
}}}

And this difference should increase exponentially when the number of vertices increases (on random graphs)

Nathann"	enhancement	closed	major	sage-4.6.1	graph theory	fixed				N/A	Robert Miller	Nathann Cohen	sage-4.6.1.alpha3