View Related Documents

Abstract

A family of sets H is ideal if the polyhedron x ≥ 0: ∑i∈S x i ≥, 1; ∀SH is integral. Consider a graph G with vertices s, t. An odd st-walk is either: an odd st-path; or the union of an even st-path and an odd circuit which share at most one vertex. Let T be a subset of vertices of even cardinality. An st-T-cut is a cut of the form δ(U) where |UT| is odd and U contains exactly one of s or t. We give excluded minor characterizations for when the families of odd st-walks and st-T-cuts (represented as sets of edges) are ideal. As a corollary we characterize which extensions and coextensions of graphic and cographic matroids are 1-flowing.
This work supported by the Fields Institute and the University of Waterloo.

Fulltext Preview

Image of the first page of the fulltext document