Bibliographic Metadata
Bibliographic Metadata
- TitleFactors in graphs : / vorgelegt von Isaak H. Wolf ; Betreuer: Prof. Dr. Eckhard Steffen
- Author
- Participants
- Published
- Description1 Online-Ressource (ix, 161 Seiten) : Diagramme
- Institutional NoteUniversität Paderborn, Dissertation, 2024
- AnnotationTag der Verteidigung: 29.08.2024
- Defended on2024-08-29
- LanguageEnglish
- Document TypesDissertation (PhD)
- URN
- DOI
Links
- Social MediaShare
- Reference
- IIIF
Files
Classification
Zusammenfassung
Faktoren in Graphen bilden ein klassisches Gebiet der Graphentheorie. Insbesondere perfekte Matchings in kubischen Graphen und reguläre Faktoren von regulären Graphen sind gut erforscht. Eine bedeutende Vermutung, die immer noch offen ist, wurde 1971 von Fulkerson formuliert und besagt, dass jeder brückenlose kubische Graph sechs perfekte Matchings hat, so dass jede Kante in genau zwei von ihnen vorkommt. Ein r-Graph, der als Verallgemeinerung eines brückenlosen kubischen Graphen angesehen werden kann, ist ein r-regulärer Graph, in dem jede ungerade Menge von Knoten mit seinem Komplement durch mindestens r Kanten verbunden ist. Ähnlich wie im kubischen Fall vermutete Seymour, dass jeder r-Graph 2r perfekte Matchings hat, so dass jede Kante in genau zwei von ihnen vorkommt. Beide Vermutungen sind trivialerweise wahr für Graphen mit chromatischem Index Delta, aber im Allgemeinen noch weitgehend offen. In dieser Arbeit stellen wir verschiedene neue Ergebnisse auf dem Gebiet der Graphenfaktoren vor; die meisten stehen in engem Zusammenhang mit den beiden oben genannten Vermutungen. Insbesondere untersuchen wir perfekte Matchings in r-Graphen. Die Hauptmotivation ist, ein besseres Verständnis der Struktur von Graphen die nicht Delta-kantenfärbbar sind, zu erlangen.
Abstract
Factors in graphs form a classical area of graph theory. In particular, perfect matchings in cubic graphs and regular factors of regular graphs are well-studied. One major conjecture that is still open was formulated by Fulkerson in 1971 and states that every bridgeless cubic graph has six perfect matchings such that each edge is in exactly two of them. An r-graph, which can be seen as a generalization of a bridgeless cubic graph, is an r-regular graph in which every odd set of vertices is connected to its complement by at least r edges. Similar to the cubic case, Seymour conjectured that every r-graph has 2r perfect matchings such that each edge is in exactly two of them. Both conjectures are trivially true for graphs with chromatic index Delta, but widely open in general. In this thesis we present various new results in the broad area of graph factors; most of them are well-related to the two aforementioned conjectures. In particular we study perfect matchings in r-graphs. The main motivation is to get a better understanding of the structure of graphs that are not Delta-edge-colorable.
Content
Stats
- The PDF-Document has been downloaded 26 times.
License/Rightsstatement
