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.