Department of
Applied
Mathematics

Packing T-joins in Planar Graphs

Katherine Edwards

Abstract

Let G be a graph and T an even sized subset of its vertices. A T-join is a subgraph of G whose odd-degree vertices are precisely those in T, and a T-cut is a cut \delta(S) where S contains an odd number of vertices of T. It has been conjectured by Guenin that if all T-cuts of G have the same parity and the size of every T-cut is at least k, then G contains k edge-disjoint T-joins. We discuss some recent progress on this conjecture and related results.