Linear Arboricity, Acyclic edge coloring

[ncohen]

This patch implements LP formulations of Linear Arboricity and Acyclic edge coloring

Nathann Thank you.I got it.

This ticket is the same as #8405. The latter got spam content and the spammer closed the ticket. It would be more trouble and result in confusion to reopen the ticket. So I have moved the ticket over to this one.

[mvngu]

For an explanation of the Linear Program used to solve this problem, see the LP chapter from :  http://code.google.com/p/graph-theory-algorithms-book/

Nathann

[rlm]

Failures:

sage -t -only-optional=glpk,cbc "devel/sage-main/sage/graphs/graph_coloring.py"
**********************************************************************
File "/Users/rlmill/sage-4.4.4.alpha0-cbc/devel/sage-main/sage/graphs/graph_coloring.py", line 749:
    sage: all([g1.has_edge(e) or g2.has_edge(e) for e in g.edges()])  # optional - GLPK, CBC
Expected:
    True
Got:
    False
**********************************************************************
File "/Users/rlmill/sage-4.4.4.alpha0-cbc/devel/sage-main/sage/graphs/graph_coloring.py", line 922:
    sage: all([ any([gg.has_edge(e) for gg in colors]) for e in g.edges()])     # optional - GLPK, CBC
Expected:
    True
Got:
    False
**********************************************************************

[ncohen]

Yet another graph constructor from networkx, with {} instead of None as labels. A g.edges(labels = False) did the trick :-)

Sorry abou that !

Nathann