Volltextdatei(en) vorhanden
Titel: The excluded minor structure theorem, and linkages in large graphs of bounded tree-width
Sonstige Titel: Der Struktursatz für verbotene Minoren und Wegverbindungen in großen Graphen beschränkter Baumweite
Sprache: Englisch
Autor*in: Müller, Theodor
Schlagwörter: Struktursatz; Verbotener Minor; Fasteinbettung; Wegverbindungen; tree-width; structure theorem; excluded minor; near-embedding; linkage
GND-Schlagwörter: Graphentheorie; Baumweite
Erscheinungsdatum: 2014
Tag der mündlichen Prüfung: 2014-03-19
Zusammenfassung: 
A central part of the graph minor theory developed by Robertson and Seymour is the excluded minor structure theorem. This theorem has found many applications elsewhere.

In the first part of this dissertation, we present a new version of this structure theorem with the goal to provide a broad feature set and an accessible terminology to allow for easier applications.

A graph G with |G|≥2k is called k-linked if for every choice of distinct vertices s_1,...,s_k,t_1,...,t_k there are disjoint paths P_1,...,P_k such that the ends of P_i are s_i and t_i. It has been shown by Larman and Mani and Jung that there exists a function f(k) such that every f(k)-connected graph is k-linked. Bollobàs and Thomason have given a linear bound of 22k. This result has been improved by Thomas and Wollan by proving that 10k-connected graphs are k-linked.

In the second part, we show that for all integers k and w there is an integer N such that every 2k+3-connected graph G of tree-width less than w on at least N vertices is k-linked. A central part of the proof is the study of certain subgraphs of G. We analyze linear decompositions of these subgraphs with new techniques we derived from those techniques used in the first part.
URL: https://ediss.sub.uni-hamburg.de/handle/ediss/5376
URN: urn:nbn:de:gbv:18-67087
Dokumenttyp: Dissertation
Betreuer*in: Diestel, Reinhard (Prof. Dr.)
Enthalten in den Sammlungen:Elektronische Dissertationen und Habilitationen

Dateien zu dieser Ressource:
Datei Beschreibung GrößeFormat  
Dissertation.pdf1.14 MBAdobe PDFÖffnen/Anzeigen
Zur Langanzeige

Diese Publikation steht in elektronischer Form im Internet bereit und kann gelesen werden. Über den freien Zugang hinaus wurden durch die Urheberin / den Urheber keine weiteren Rechte eingeräumt. Nutzungshandlungen (wie zum Beispiel der Download, das Bearbeiten, das Weiterverbreiten) sind daher nur im Rahmen der gesetzlichen Erlaubnisse des Urheberrechtsgesetzes (UrhG) erlaubt. Dies gilt für die Publikation sowie für ihre einzelnen Bestandteile, soweit nichts Anderes ausgewiesen ist.

Info

Seitenansichten

23
Letzte Woche
Letzten Monat
geprüft am 15.04.2021

Download(s)

6
Letzte Woche
Letzten Monat
geprüft am 15.04.2021
Werkzeuge

Google ScholarTM

Prüfe