Charlotte Knierim Long Cycles, Heavy Cycles and Cycle Decompositions in Directed Graphs

The talk Long Cycles, Heavy Cycles and Cycle Decompositions in Directed Graphs by Charlotte Knierim on the Moscow Conference on Combinatorics and Applications at MIPT. Annotation: In this talk I show a connection between heavy cycles and cycle decompositions. We prove that every directed Eulerian graph can be decomposed into at most O(n log Δ) disjoint cycles, thus making progress towards the conjecture by Bollobás and Scott, and matching the best known upper bound from the undirected case. This also implies the existence of long cycles differing to the ErdősGallai bound for undirected graphs in only a log factor Our approach is based on finding heavy cycles in certain edgeweightings of directed graphs. As a further consequence of our techniques, we prove that for every edgeweighted digraph in which every vertex has outweight at least 1, there exists a cycle with weight at least Ω(log log n, log n), thus resolving a question by Bollobás and Scott. Aditionally