**Discrete Mathematics and Optimization Seminar**

**DAVID WOOD**

* Carleton University *

Monday March 8th at 4.30pm

* Burnside 1205*

**Title. *** Bounded Degree Acyclic Decompositions of Digraphs.*

**Abstract. **
An acyclic decomposition of a digraph is a partition of
the edges into acyclic subgraphs. Trivially every digraph

has an acyclic decomposition into two subgraphs. We are
interested in acyclic decompositions in which each subgraph

has bounded degree. It is proved that for every integer *s >= 2*,
every digraph has an acyclic decomposition into *s* subgraphs such

that in each subgraph the outdegree of every vertex *v *is at most
*ceil(outdegree(v)/(s-1))*. For all digraphs this bound is
optimal.