Cycles in directed graphs
|
Tue, 10/03/2009 14:30 |
Peter Keevash (QMUL) |
Combinatorial Theory Seminar  |
L3 |
| 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. | |||