Graphs and Matroids Seminar - Jim Geelen

Title: The Erdős-Pósa property for A-paths

Abstract:

Let A be a set of vertices in a graph G. An A-path is a path whose ends are in A. Gallai proved, for any integer k, that there are either k disjoint A-paths or there is a set of at most 2k vertices that hit all A-paths.There are a number of extensions of this result where we want disjoint paths chosen from some "allowable" collection of prescribed A-paths; for example, in one of these results the allowable paths are those of odd length. We discuss a common generalization of all of these results in which the collection of allowable A-paths is somewhat arbitrary, but is required to satisfy a natural "exchange property".

This is joint work with Sergey Norin.