10 March 2009
There are many theorems concerning cycles in graphs for which it is natural to seek analogous results for directed graphs. I will survey recent progress on certain questions of this type. New results include (i) a solution to a question of Thomassen on an analogue of Dirac’s theorem for oriented graphs, (ii) a theorem on packing cyclic triangles in tournaments that “almost” answers a question of Cuckler and Yuster, and (iii) a bound for the smallest feedback arc set in a digraph with no short directed cycles, which is optimal up to a constant factor and extends a result of Chudnovsky, Seymour and Sullivan. These are joint work respectively with (i) Kuhn and Osthus, (ii) Sudakov, and (iii) Fox and Sudakov.
- Combinatorial Theory Seminar