Detailansicht
Nowhere-zero flows and structures in cubic graphs
Arthur Hoffmann-Ostenhof
Art der Arbeit
Dissertation
Universität
Universität Wien
Fakultät
Fakultät für Mathematik
Betreuer*in
Herbert Fleischner
DOI
10.25365/thesis.19501
URN
urn:nbn:at:at-ubw:1-29452.01997.398662-7
Link zu u:search
(Print-Exemplar eventuell in Bibliothek verfügbar)
Abstracts
Abstract
(Deutsch)
Wir widerlegen zwei Vermutungen, die im Zusammenhang mit Kreisüberdeckungen von kubischen Graphen stehen. Die erste Vermutung, welche kubische Graphen mit dominierenden Kreisen betrifft, widerlegen wir durch Erweiterung eines Theorems von Gallai über induzierte eulersche Graphen und durch Konstruktion spezieller snarks. Die zweite Vermutung, welche frames betrifft, widerlegen wir durch Betrachtung der Frage nach der Existenz von speziellen spannenden Teilgraphen in 3-fach zusammenhängenden kubischen Graphen. Weiters übersetzen wir Probleme über Flüsse in kubischen Graphen in Knotenfärbungsprobleme von planaren Graphen und erhalten eine neue Charakterisierung von snarks. Schliesslich verbessern und erweitern wir Resultate über Knotenfärbungsprobleme in Quadrangulierungen. Zu Ende stellen wir neue Vermutungen auf, die im Zusammenhang mit Kreisüberdeckungen und Strukturen in kubischen Graphen stehen.
Abstract
(Englisch)
We disprove two conjectures which are related to cycle double cover problems. The first conjecture concerns cubic graphs with dominating cycle. We disprove this conjecture by extending a result of Gallai about induced eulerian subgraphs and by constructing special snarks. The second conjecture concerns frames. We show that this conjecture is false by considering the problem whether every 3-connected cubic graph has a spanning subgraph with certain properties. Moreover, we transform flow-problems of cubic graphs into vertex coloring problems of plane graphs. We obtain thereby a new characterization of snarks. Furthermore, we improve and extend results about vertex coloring problems of quadrangulations. Finally we pose new problems and state conjectures which are related to cycle double covers and structures in cubic graphs.
Schlagwörter
Schlagwörter
(Englisch)
cycle double cover cubic graph frame mosaic nowhere-zero flow dominating cycle vertex coloring quadrangulation snark 3-edge coloring induced eulerian subgraph generalized even 2-factor bipartizing matching 6-flow
Schlagwörter
(Deutsch)
kubisch planar Kreisüberdeckung Fluss Mosaik dominierender Kreis Knotenfärbung Quadrangulierung snark bipartizing matching
Autor*innen
Arthur Hoffmann-Ostenhof
Haupttitel (Englisch)
Nowhere-zero flows and structures in cubic graphs
Paralleltitel (Deutsch)
Flüsse und Strukturen in kubischen Graphen
Publikationsjahr
2011
Umfangsangabe
76 S. : graph. Darst.
Sprache
Englisch
Beurteiler*innen
Martin Kochol ,
Bernhard Krön
Klassifikation
31 Mathematik > 31.12 Kombinatorik, Graphentheorie
AC Nummer
AC08958823
Utheses ID
17436
Studienkennzahl
UA | 791 | 405 | |