×

zbMATH — the first resource for mathematics

Disjoint directed cycles. (English) Zbl 0861.05037
It is shown that there exists a positive \(\varepsilon\) so that for any integer \(k\), every directed graph with minimum outdegree at least \(k\) contains at least \(\varepsilon k\) vertex disjoint cycles. On the other hand, for every \(k\) there is a digraph with minimum outdegree \(k\) which does not contain two vertex or edge disjoint cycles of the same length.
Reviewer: N.Alon (Tel Aviv)

MSC:
05C38 Paths and cycles
05C20 Directed graphs (digraphs), tournaments
PDF BibTeX XML Cite
Full Text: DOI