Matching minors in bipartite graphs

In der vorliegenden Arbeit werden fundamentale Teile des Graphminorenprojekts von Robertson und Seymour für das Studium von Matching Minoren adaptiert und Verbindungen zur Strukturtheorie gerichteter Graphen aufgezeigt. Wir entwickeln matchingtheoretische Analogien zu etablierten Resultaten des Graphminorenprojekts:Wir charakterisieren die Existenz eines Kreuzes über einem konformen Kreis mittels topologischer Eigenschaften. Weiter entwickeln wir eine Theorie zu perfekter Matchingweite, einem Weiteparameter für Graphen mit perfekten Matchings, der von Norin eingeführt wurde. Hier zeigen wir, dass das Disjunkte Alternierende Pfade Problem auf bipartiten Graphen mit beschränkter Weite in Polynomialzeit lösbar ist. Weiter zeigen wir, dass jeder bipartite Graph mit hoher perfekter Matchingweite ein großes Gitter als Matchingminor enthalten muss. Schließlich zeigen wir ein Analogon des bekannten Flat Wall Theorem und geben eine qualitative Beschreibung aller bipartiter Graphen an, die einen festen Matching Minor ausschließen.