Bounded degree acyclic decompositions of digraphs

Research output: Contribution to journalArticleResearchpeer-review

4 Citations (Scopus)

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. 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 each vertex v is at most ⌈deg(v)/s-1⌉. For all digraphs this degree bound is optimal.
Original languageEnglish
Pages (from-to)309-313
Number of pages5
JournalJournal of Combinatorial Theory, Series B
Volume90
Issue number2
DOIs
Publication statusPublished - 2004
Externally publishedYes

Cite this