Spelling suggestions: "subject:"snares"" "subject:"snarast""
1 |
Measurements of edge uncolourability in cubic graphsAllie, Imran January 2020 (has links)
Philosophiae Doctor - PhD / The history of the pursuit of uncolourable cubic graphs dates back more than a century.
This pursuit has evolved from the slow discovery of individual uncolourable
cubic graphs such as the famous Petersen graph and the Blanusa snarks, to discovering
in nite classes of uncolourable cubic graphs such as the Louphekine and
Goldberg snarks, to investigating parameters which measure the uncolourability of
cubic graphs. These parameters include resistance, oddness and weak oddness,
ow
resistance, among others. In this thesis, we consider current ideas and problems regarding
the uncolourability of cubic graphs, centering around these parameters. We
introduce new ideas regarding the structural complexity of these graphs in question.
In particular, we consider their 3-critical subgraphs, speci cally in relation to resistance.
We further introduce new parameters which measure the uncolourability of
cubic graphs, speci cally relating to their 3-critical subgraphs and various types of
cubic graph reductions. This is also done with a view to identifying further problems
of interest. This thesis also presents solutions and partial solutions to long-standing
open conjectures relating in particular to oddness, weak oddness and resistance.
|
2 |
Pokrývání kubických grafů párováními / Matching covers of cubic graphsSlívová, Veronika January 2017 (has links)
Berge and Fulkerson conjectured that for each cubic bridgeless graph there are six perfect matchings such that each edge is contained in exactly two of them. Another conjecture due to Berge says that we can cover cubic bridgeless graphs by five perfect matchings. Both conjectures are studied for over forty years. Abreu et al. [2016] introduce a new class of graphs (called treelike snarks) which cannot be covered by less then five perfect matchings. We show that their lower bound on number of perfect matchings is tight. Moreover we prove that a bigger class of cubic bridgeless graphs admits Berge conjecture. Finally, we also show that Berge-Fulkerson conjecture holds for treelike snarks.
|
3 |
Snarks : Generation, coverings and colouringsHägglund, Jonas January 2012 (has links)
For a number of unsolved problems in graph theory such as the cycle double cover conjecture, Fulkerson's conjecture and Tutte's 5-flow conjecture it is sufficient to prove them for a family of graphs called snarks. Named after the mysterious creature in Lewis Carroll's poem, a \emph{snark} is a cyclically 4-edge connected 3-regular graph of girth at least 5 which cannot be properly edge coloured using three colours. Snarks and problems for which an edge minimal counterexample must be a snark are the central topics of this thesis. The first part of this thesis is intended as a short introduction to the area. The second part is an introduction to the appended papers and the third part consists of the four papers presented in a chronological order. In Paper I we study the strong cycle double cover conjecture and stable cycles for small snarks. We prove that if a bridgeless cubic graph $G$ has a cycle of length at least $|V(G)|-9$ then it also has a cycle double cover. Furthermore we show that there exist cyclically 5-edge connected snarks with stable cycles and that there exists an infinite family of snarks with stable cycles of length 24. In Paper II we present a new algorithm for generating all non-isomorphic snarks with a given number of vertices. We generate all snarks on 36 vertices and less and study these with respect to various properties. We find that a number of conjectures on cycle covers and colourings holds for all graphs of these orders. Furthermore we present counterexamples to no less than eight published conjectures on cycle coverings, cycle decompositions and the general structure of regular graphs. In Paper III we show that Jaeger's Petersen colouring conjecture holds for three infinite families of snarks and that a minimum counterexample to this conjecture cannot contain a certain subdivision of $K_{3,3}$ as a subgraph. Furthermore, it is shown that one infinite family of snarks have strong Petersen colourings while another does not have any such colourings. Two simple constructions for snarks with arbitrary high oddness and resistance is given in Paper IV. It is observed that some snarks obtained from this construction have the property that they require at least five perfect matchings to cover the edges. This disproves a suggested strengthening of Fulkerson's conjecture.
|
Page generated in 0.0227 seconds