Forbidding odd K3,3 as a graft minor

Abstract

A graph is odd−K5 free if K5 cannot be obtained by deleting edges and then contracting all edges in a cut. odd − K5 free graphs play an important role in the study of multi-commodity flows. A graph is odd − K3,3 free if K3,3 cannot be obtained by contracting edges and then deleting all edges in an eulerian subgraph. A long-standing conjecture of Paul Seymour predicts that postman sets pack in odd − K3,3 free graphs. We study odd − K3,3 free graphs that are almost planar in this thesis and discuss the relation to Seymour’s conjecture.