In dieser Arbeit werden Dualitäten in gerichteten und ungerichteten Graphen untersucht, wobei Konzepte wie Weiteparameter, Obstruktionen und Substrukturen eine zentrale Rolle spielen. Der Schwerpunkt liegt auf der Struktur gerichteter Graphen. Im Rahmen einer lange bestehenden Vermutung über die Monotoniekosten einer Variante des Räuber und Gendarm Spiels für gerichtete Graphen werden neue Weiteparameter eingeführt, die auf gerichteten Separationen basieren und eng mit der DAG-Weite verbunden sind. Tangle-artige Obstruktionen zu diesen Weiteparametern werden identifiziert, und die Dualität zwischen diesen Konzepten wird bewiesen. Die gerichtete Baumweite, eine Verallgemeinerung der Baumweite für ungerichtete Graphen, wird vorgestellt, und ein neuer Weiteparameter, die Cyclewidth, wird als parametrisch äquivalent zur gerichteten Baumweite eingeführt. Zudem wird die Beziehung zwischen gerichteten und bipartiten Graphen mit perfekten Matchings genutzt, um gerichtete Graphen mit kleiner Cyclewidth zu charakterisieren. Aufbauend auf dem Strukturtheorem von Robertson und Seymour wird ein neues Flat-wall-Theorem für gerichtete Graphen bewiesen, das als Grundlage für ein zukünftiges gerichtetes Strukturtheorem dienen soll. Darüber hinaus werden Ergebnisse zu induzierten Subgraphen in ungerichteten Graphen und deren Linegraphen präsentiert, die von spezifischen Graphklassen bis hin zur allgemeinen Klasse aller Graphen reichen.
Meike Hatzel Bücher
