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 sgreater than or equal to2 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. (C) 2003 Elsevier Inc. All rights reserved. [References: 7]
展开▼
