Viele schwere Probleme in der Graphentheorie können auf kubische Graphen reduziert werden. Für die meisten Probleme sind mögliche minimale Gegenbeispiele aus der Klasse der brückenlosen nicht 3-kantenfärbbaren kubischen Graphen. Diese Graphen wurden von Gardner als Snarks bezeichnet. Eine hauptsächliche Schwierigkeit bei den Beweisen von Theoremen für Snarks ist das Finden von geeigneten Strukturparametern für den Beweis. Eine Herangehensweise ist es Invarianten zu studieren, die ,,messen" wie weit ein kubischer Graph davon entfernt ist 3-kantenfarbbar zu sein; solche Invarianten werden auch Unfärbbarkeitsparameter genannt. In der Arbeit wird eine Theorie der Kerne von Snarks und dem dazugehorigen Parameter 3 entwickelt. Die Ergebnisse führen zu weiteren Ergebnissen zur Vermutung von Fan, Raspaud und zur Petersen Färbungsvermutung. Weiterhin wird 3 in Beziehung zu anderen Unfärbbarkeitsparametern gesetzt. Die Theorie der Kerne wird zum einen auf schwache Kerne verallgemeinert und es werden aquivalente Formulierungen der Fano-Flussvermutungen abgeleitet. Zum anderen wird sie auf r-Graphen verallgemeinert was eine Verallgemeinerung der Fan-Raspaud Vermutung fur r-Graphen ermöglicht. Weiterhin wird Vizings Vermutung für planare Graphen studiert.
Titelaufnahme
- TitelCovers and cores of r-graphs / by Ligang Jin ; Adviser: Prof. Dr. Eckhard Steffen
- Autor
- Beteiligte
- Erschienen
- AusgabeElektronische Ressource
- Umfang1 Online-Ressource (xviii, 117 Seiten)
- HochschulschriftUniversität Paderborn, Dissertation, 2017
- AnmerkungTag der Verteidigung: 17.07.2017
- Verteidigung2017-07-17
- SpracheEnglisch
- DokumenttypDissertation
- URN
- DOI
- Social MediaShare
- Nachweis
- IIIF
There are many hard problems in graph theory, such as the Four Color Problem, which can besolved in the general case if they are solvable for cubic graphs. Possible minimal counterexamplesfor most of these problems are asked to be snarks. An effective approach to prove theorems for snarks is by measures of edge-uncolorability. The thesis develops theory of cores and the related measure 3 for cubic graphs, first introduced by Steffen. The theory is applied to prove further results to both Fan-Raspaud conjecture and Petersen coloring conjecture, for which there are very few results known. Relations between 3 and other measures, especially the oddness, are given. Moreover, the theory of cores are extended to weak cores, which are then related to Fano-flows. It is also extend to cores of r-graphs. This gives us two benefits, one is to pose the generalized Fan-Raspaud conjecture from the viewpoint of cores, and the other is to define the rst measure for r-graphs. Finally, the thesis proves partial results to the generalized Berge conjecture and to Vizing's planar graph conjecture.
- Das PDF-Dokument wurde 22 mal heruntergeladen.