Wednesday, June 19

4:00 PM
## IP6

A Proof of Younger's Conjecture on Disjoint Directed Circuits

Chair: Jennifer Zito, Center for Computing Sciences
What could cause a directed graph not to possess many pairwise vertex-disjoint directed circuits? It might be that there is a small set of vertices so that every directed circuit passes through at least one of these vertices. In 1973 Younger conjectured that there was no other possible cause; more precisely, that in in every digraph without many disjoint directed circuits there is a small set of vertices meeting all directed circuits. We sketch a recent proof of this conjecture.This is joint work with Bruce Reed, Neil Robertson and Robin Thomas.

**Paul D. Seymour**

Bellcore

*MEM, 4/10/96*