School Seminars and Colloquia

The two disjoint rooted paths problem

Discrete Structures and Algorithms (Reading Group): Graph Minors

by Gwena\"el Joret

Institution: Universit\'e Libre de Bruxelles
Date: Mon 26th September 2011
Time: 11:00 AM
Location: Room 107, Richard Berry Building

Abstract: Given four distinct vertices $s_1, s_2, t_1, t_2$ of a graph $G$, Menger's theorem tells us exactly when there exist two vertex-disjoint paths in $G$ between $\{s_1, s_2\}$ and $\{t_1, t_2\}$: the obvious necessary condition is sufficient. But what if we moreover require that these two paths link $s_1$ to $t_1$ and $s_2$ to $t_2$? Here the answer is less straightforward, the paths exist if and only if a certain auxiliary graph contains a special kind of $K_5$ minor. I will present this result and its proof at the next meeting.