# Ticket #8748(closed enhancement: fixed)

Opened 3 years ago

## Linear Arboricity, Acyclic edge coloring

Reported by: Owned by: ncohen jason, ncohen, rlm major sage-4.5 graph theory N/A Robert Miller Nathann Cohen sage-4.5.alpha1

### Description

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.

## Change History

### comment:1 Changed 3 years ago by mvngu

• Status changed from new to needs_review

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

### comment:2 Changed 3 years ago by rlm

• Status changed from needs_review to needs_work
• Reviewers set to Robert Miller
• Authors set to Nathann Cohen

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
**********************************************************************
```

### comment:3 Changed 3 years ago by ncohen

• Status changed from needs_work to needs_review

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

Sorry abou that !

Nathann

### comment:4 Changed 3 years ago by rlm

• Status changed from needs_review to positive_review

### comment:5 Changed 3 years ago by rlm

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