umu.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Snarks: Generation, coverings and colourings
Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
2012 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

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.

Place, publisher, year, edition, pages
Umeå: Umeå universitet , 2012. , 69 p.
Series
Doctoral thesis / Umeå University, Department of Mathematics, ISSN 1102-8300 ; 53
Keyword [en]
Snarks, cubic graphs, enumeration, cycle covers, perfect matching covers, Fulkerson's conjecture, strong cycle double cover conjecture, cycle decompositions, stable cycles, oddness, circumference, uncolourability measures
National Category
Discrete Mathematics
Research subject
Mathematics
Identifiers
URN: urn:nbn:se:umu:diva-53337ISBN: 978-91-7459-399-0 (print)OAI: oai:DiVA.org:umu-53337DiVA: diva2:511537
Public defence
2012-04-13, MIT-huset, MA121, Umeå universitet, Umeå, 13:15 (English)
Opponent
Supervisors
Available from: 2012-03-23 Created: 2012-03-21 Last updated: 2013-09-05Bibliographically approved
List of papers
1. On stable cycles and cycle double covers of graphs with large circumference
Open this publication in new window or tab >>On stable cycles and cycle double covers of graphs with large circumference
2012 (English)In: Discrete Mathematics, ISSN 0012-365X, E-ISSN 1872-681X, Vol. 312, no 17, 2540-2544 p.Article in journal (Refereed) Published
Abstract [en]

A cycle C in a graph is called stable if there exists no other cycle D in the same graph such that V(C)⊆V(D). In this paper, we study stable cycles in snarks and we show that if a cubic graph G has a cycle of length at least |V(G)|−9 then it has a cycle double cover. We also give a construction for an infinite snark family with stable cycles of constant length and answer a question by Kochol by giving examples of cyclically 5-edge connected snarks with stable cycles.

Place, publisher, year, edition, pages
Elsevier, 2012
Keyword
Stable cycle, Snark, Cycle double cover, Semiextension
National Category
Discrete Mathematics
Research subject
Mathematics
Identifiers
urn:nbn:se:umu:diva-53282 (URN)10.1016/j.disc.2011.08.024 (DOI)000306873100004 ()
Conference
the 8th French Combinatorial Conference, 28 June - 2 July, 2010, Paris
Note

Special Issue: Proceedings of the 8th French Combinatorial Conference

Available from: 2012-03-21 Created: 2012-03-19 Last updated: 2017-12-07Bibliographically approved
2. Generation and properties of snarks
Open this publication in new window or tab >>Generation and properties of snarks
2013 (English)In: Journal of combinatorial theory. Series B (Print), ISSN 0095-8956, E-ISSN 1096-0902, Vol. 103, no 4, 468-488 p.Article in journal (Refereed) Published
Abstract [en]

For many of the unsolved problems concerning cycles and matchings in graphs it is known that it is sufficient to prove them for snarks, the class of non-trivial 3-regular graphs which cannot be 3-edge coloured.

In the first part of this paper we present a. new algorithm for generating all non-isomorphic snarks of a given order. Our implementation of the new algorithm is 14 times faster than previous programs for generating snarks, and 29 times faster for generating weak snarks. Using this program we have generated all non-isomorphic snarks on n <= 36 vertices. Previously lists up to n = 28 vertices have been published.

In the second part of the paper we analyze the sets of generated snarks with respect to a number of properties and conjectures. We find that some of the strongest versions of the cycle double cover conjecture hold for all snarks of these orders, as does Jaeger's Petersen colouring conjecture, which in turn implies that Fulkerson's conjecture has no small counterexamples. In contrast to these positive results we also find counterexamples to eight previously published conjectures concerning cycle coverings and the general cycle structure of cubic graphs.

(C) 2013 Published by Elsevier Inc.

Keyword
Snarks, Cycle double covers, Shortest cycle covers, Computer generation
National Category
Mathematics
Identifiers
urn:nbn:se:umu:diva-79263 (URN)10.1016/j.jctb.2013.05.001 (DOI)000321725600004 ()
Available from: 2013-09-05 Created: 2013-08-13 Last updated: 2017-12-06Bibliographically approved
3. Petersen-colorings and some families of snarks
Open this publication in new window or tab >>Petersen-colorings and some families of snarks
2014 (English)In: Ars Mathematica Contemporanea, ISSN 1855-3966, Vol. 7, no 1, 161-173 p.Article in journal (Other academic) Published
Abstract [en]

In this paper we study Petersen-colorings and strong Petersen-colorings on some well known families of snarks, e.g. Blanusa snarks, Goldberg snarks and flower snarks. In particular, it is shown that flower snarks have a Petersen-coloring but they do not have a strong Petersen-coloring. Furthermore it is proved that possible minimum counterexamples to Jaeger's Petersen-coloring conjecture do not contain a specific subdivision of K-3,K-3.

Keyword
Petersen colorings, snarks
National Category
Discrete Mathematics
Research subject
Mathematics
Identifiers
urn:nbn:se:umu:diva-53324 (URN)000320236500013 ()
Available from: 2012-03-21 Created: 2012-03-21 Last updated: 2017-12-07Bibliographically approved
4. On snarks that are far from being 3-edge colorable
Open this publication in new window or tab >>On snarks that are far from being 3-edge colorable
(English)Manuscript (preprint) (Other academic)
Abstract [en]

In this note we construct two infinite snark families which have high oddness and low circumference compared to the number of vertices.     Using this construction, we also give a counterexample to a suggested strengthening of Fulkerson's conjecture by showing that the Petersen graph is not the only cyclically 4-edge connected cubic graph which require at least five perfect matchings to cover its edges. Furthermore the counterexample presented has the interesting property that no 2-factor can be part of a cycle double cover.

Keyword
Snarks, 3-edge colourings, oddness, resistance, circumference, cycle double covers, perfect matching covers
National Category
Discrete Mathematics
Research subject
Mathematics
Identifiers
urn:nbn:se:umu:diva-53323 (URN)
Available from: 2012-03-21 Created: 2012-03-21 Last updated: 2012-03-22Bibliographically approved

Open Access in DiVA

fulltext(2341 kB)1205 downloads
File information
File name FULLTEXT01.pdfFile size 2341 kBChecksum SHA-512
18771dea6497bdc35f828819aaab70ef78c1c058f3292992962e7762dbd2e679c3ef27ec9ddeaa8ae8245b435bfffd3d785e7c53f36cc6345dc8bc9a30219017
Type fulltextMimetype application/pdf

Authority records BETA

Hägglund, Jonas

Search in DiVA

By author/editor
Hägglund, Jonas
By organisation
Department of Mathematics and Mathematical Statistics
Discrete Mathematics

Search outside of DiVA

GoogleGoogle Scholar
Total: 1205 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 439 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf