Volltextdatei(en) vorhanden
Titel: Structural properties of dense graphs with high odd girth and packing of minor-closed families of graphs
Sonstige Titel: Struktur dichter Graphen mit hoher Taillenweite und Packungen unter Minorenbildung abgeschlossener Graphenfamilien
Sprache: Englisch
Autor*in: Messuti, Silvia
Erscheinungsdatum: 2016
Tag der mündlichen Prüfung: 2016-07-07
Zusammenfassung: 
We present two results that concern different aspects of extremal graph theory.
In the first part we study minimum degree conditions for which a graph with given odd girth is homomorphic to its smallest odd cycle. This is motivated by a classical result of Andrásfai, Erdős, and Sós which states that every n-vertex graph with odd girth at least 2k+1 and minimum degree larger than 2n/(2k+1) is bipartite. Since the cycle of length 2k+1 is an extremal graph for this problem, we asked whether a weaker degree condition implies the existence of a homomorphism into C_(2k+1). We show that this happens for any n-vertex graph with odd girth 2k+1 and minimum degree larger than 3n/4k and give a detailed description of the extremal graphs.
The second part of our work is dedicated to a packing problem that has its roots in Gyárfás’ Tree Packing Conjecture. This conjecture states that a sequence of n trees (T_1, ..., T_n) with v(T_i)=i packs into K_n. An asymptotic version of this conjecture in which trees with bounded maximum degree are packed into K_(1+o(1))n was recently proved. We generalise this result from sequences of trees to sequences of graphs from any non-trivial minor-closed class.

Wir stellen zwei Ergebnisse vor, die verschiedene Aspekte der extremalen Graphentheorie betreffen.
Im ersten Teil untersuchen wir Minimalgradbedingungen für die ein Graph mit gegebener ungerader Taillenweite homomorph zu dem kleinsten ungeraden Kreis ist, den er enthält. Diese Frage ist durch ein Resultat von Andrásfai, Erdős, und Sós motiviert, welches besagt, dass jeder Graph auf n Ecken mit ungerader Taillenweite mindestens 2k+1 und Minimalgrad größer als 2n/(2k+1) bipartit ist. Da der Kreis auf 2k+1 Ecken ein extremaler Graph für dieses Problem ist, untersuchen wir ob eine schwächere Minimalgradbedingung die Existenz eines Homomorphismus in C_(2k+1) impliziert. Wir zeigen, dass dies für Graphen auf n Ecken mit ungerader Taillenweite 2k+1 und Minimalgrad größer als 3n/4k gilt und beschreiben die extremalen Graphen im Detail.
Im zweiten Teil untersuchen wir ein Packungsproblem, dass seinen Ursprung in der Baumpackungsvermutung von Gyárfás hat. Diese Vermutung besagt, dass jede Folge von Bäumen (T_1, ..., T_n) mit v(T_i)=i sich in den K_n packen lässt. Eine asymptotische Variante dieser Vermutung, in der Bäume mit beschränktem Maximalgrad in K_(1+o(1))n gepackt werden, wurde kürzlich gezeigt. Wir verallgemeinern dieses Resultat auf Folgen von Graphen mit beschränktem Maximalgrad aus jeder beliebigen nicht-trivialen unter Minorenbildung abgeschlossenen Graphenklasse.
URL: https://ediss.sub.uni-hamburg.de/handle/ediss/6959
URN: urn:nbn:de:gbv:18-81825
Dokumenttyp: Dissertation
Betreuer*in: Schacht, Mathias (Prof. PhD)
Enthalten in den Sammlungen:Elektronische Dissertationen und Habilitationen

Dateien zu dieser Ressource:
Datei Beschreibung Prüfsumme GrößeFormat  
Dissertation.pdf018d1f323e808c398207b5ebaa93ae101.51 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

302
Letzte Woche
Letzten Monat
geprüft am 28.03.2024

Download(s)

47
Letzte Woche
Letzten Monat
geprüft am 28.03.2024
Werkzeuge

Google ScholarTM

Prüfe