Title (eng)
Nowhere-zero flows and structures in cubic graphs
Parallel title (deu)
Flüsse und Strukturen in kubischen Graphen
Author
Arthur Hoffmann-Ostenhof
Advisor
Herbert Fleischner
Assessor
Martin Kochol
Bernhard Krön
Abstract (deu)
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 (eng)
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.
Keywords (eng)
cycle double covercubic graphframemosaicnowhere-zero flowdominating cyclevertex coloringquadrangulationsnark3-edge coloringinduced eulerian subgraphgeneralized even 2-factorbipartizing matching6-flow
Keywords (deu)
kubischplanarKreisüberdeckungFlussMosaikdominierender KreisKnotenfärbungQuadrangulierungsnarkbipartizing matching
Subject (deu)
Type (deu)
Persistent identifier
https://phaidra.univie.ac.at/o:1284457
rdau:P60550 (deu)
76 S. : graph. Darst.
Number of pages
76
Association (deu)
Title (eng)
Nowhere-zero flows and structures in cubic graphs
Parallel title (deu)
Flüsse und Strukturen in kubischen Graphen
Author
Arthur Hoffmann-Ostenhof
Abstract (deu)
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 (eng)
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.
Keywords (eng)
cycle double covercubic graphframemosaicnowhere-zero flowdominating cyclevertex coloringquadrangulationsnark3-edge coloringinduced eulerian subgraphgeneralized even 2-factorbipartizing matching6-flow
Keywords (deu)
kubischplanarKreisüberdeckungFlussMosaikdominierender KreisKnotenfärbungQuadrangulierungsnarkbipartizing matching
Subject (deu)
Type (deu)
Persistent identifier
https://phaidra.univie.ac.at/o:1284458
Number of pages
76
Association (deu)
License
Citable links
Other links
Managed by
Details
Metadata
Export formats
Universitätsring 1, 1010 Wien | T
T +43-1-4277-0