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

Registration | Hotel Information | Dormitory Information | Transportation | Speaker Index


MEM, 4/10/96