Long cycles, Heavy Cycles and Cycle Decompositions in Digraphs

by Charlotte Knierim

Abstract:

Hajós conjectured in 1968 that every Eulerian $n$ -vertex graph can be decomposed into at most $\lfloor (n-1)/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ás and Scott (1996) it was analogously conjectured that every directed Eulerian graph can be decomposed into $O(n)$ cycles.

In this talk, 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ás 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ás and Scott.

This is joint work with Maxime Larcher, Anders Martinsson and Andreas Noever.

Event Timeslots (1)

Friday
3:30 pm - 3:55 pm
Charlotte Knierim