Bounded degree acyclic decompositions of digraphs. (English) Zbl 1033.05087

Summary: 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 \geqslant 2\) every digraph has an acyclic decomposition into \(s\) subgraphs such that in each subgraph the outdegree of each vertex \(v\) is at most \(\left\lceil \frac {\text{deg}(v)}{s-1} \right\rceil\). For all digraphs this degree bound is optimal.


05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C20 Directed graphs (digraphs), tournaments
Full Text: DOI


[1] T. Biedl, T. Chan, Y. Ganjali, M. Hajiaghayi, D.R. Wood, Balanced vertex-orderings of graphs, Technical Report TR-2002-01, School of Computer Science, Carleton University, Ottawa, Canada, submiited for publication. · Zbl 1060.05088
[2] Biedl, T.C.; Kaufmann, M., Area-efficient static and incremental graph drawings, (), 37-52
[3] Karejan, Z.A., Arboricity of digraphs, Trudy vychisl. tsentra akad. nauk armyan. SSR i erevan. GoS. univ. mat. voprosy kibernet. i vychisl. tekhn. teoriya grafov, 9, 59-63, (1979)
[4] Markosyan, S.E.; Gasparyan, G.S., Optimal decomposition of directed multigraphs into a diforest, Metody diskret. analiz., 43, 75-86, (1986) · Zbl 0693.05055
[5] Markosjan, A.G.; Markosjan, S.E., Algorithm for the decomposition of a digraph into a diforest, Akad. nauk armyan. SSR dokl., 65, 3, 129-131, (1997)
[6] Nakayama, A.; PĂ©roche, B., Linear arboricity of digraphs, Networks, 17, 1, 39-53, (1987) · Zbl 0649.05029
[7] Wood, D.R., Optimal three-dimensional orthogonal graph drawing in the general position model, Theoret. comput. sci., 299, 1-3, 151-178, (2003) · Zbl 1040.68069
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.