Long Cycles, Heavy Cycles and Cycle Decompositions in Digraphs

Haj'os conjectured in 1968 that every Eulerian $n$-vertex graph can be decomposed into at most $\lfloor (n-1)\mathrm{/}2\rfloor$ edge-disjoint cycles. This has been confirmed for some special graph classes, but the general case remains open. In a sequence of papers by Bienia and Meyniel (1986), Dean (1986), and Bollob'as and Scott (1996) it was analogously conjectured that every \emph{directed} Eulerian graph can be decomposed into $O(n)$ cycles. In this paper, we show that every directed Eulerian graph can be decomposed into $O(n \log \Delta)$ disjoint cycles, thus making progress towards the conjecture by Bollob'as and Scott. Our approach is based on finding heavy cycles in certain edge-weightings of directed graphs. As a further consequence of our techniques, we prove that for every edge-weighted digraph in which every vertex has out-weight at least $1$, there exists a cycle with weight at least $\Omega(\log \log n/{\log n})$, thus resolving a question by Bollob'as and Scott.