© 2015 Staats- und Universitätsbibliothek
Hamburg, Carl von Ossietzky

Öffnungszeiten heute09.00 bis 24.00 Uhr alle Öffnungszeiten

Eingang zum Volltext in OPUS

Hinweis zum Urheberrecht

Dissertation zugänglich unter
URN: urn:nbn:de:gbv:18-67087
URL: http://ediss.sub.uni-hamburg.de/volltexte/2014/6708/

The excluded minor structure theorem, and linkages in large graphs of bounded tree-width

Der Struktursatz für verbotene Minoren und Wegverbindungen in großen Graphen beschränkter Baumweite

Müller, Theodor

 Dokument 1.pdf (1.141 KB) 

SWD-Schlagwörter: Graphentheorie , Baumweite
Freie Schlagwörter (Deutsch): Struktursatz , Verbotener Minor , Fasteinbettung , Wegverbindungen
Freie Schlagwörter (Englisch): tree-width , structure theorem , excluded minor , near-embedding , linkage
Basisklassifikation: 31.12
Institut: Mathematik
DDC-Sachgruppe: Mathematik
Dokumentart: Dissertation
Hauptberichter: Diestel, Reinhard (Prof. Dr.)
Sprache: Englisch
Tag der mündlichen Prüfung: 19.03.2014
Erstellungsjahr: 2014
Publikationsdatum: 17.04.2014
Kurzfassung auf Englisch: 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.


keine Statistikdaten vorhanden