Title: The Erdős-Pósa property for A-paths
|Affiliation:||University of Waterloo|
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.
200 University Avenue West
Waterloo, ON N2L 3G1