Snarks: Generation, coverings and colourings

↓ Direkt till sidans innehåll
↓ Direkt till sidans sekundära innehåll (sidomenyn)

Search: onr:"swepub:oai:DiVA.org:umu-174687" > Snarks :

1 of 1
Previous record
Next record
To hitlist

Snarks : Generation, coverings and colourings

Hägglund, Jonas, 1982- (author): Umeå universitet,Institutionen för matematik och matematisk statistik

Häggkvist, Roland, Professor (thesis advisor): Umeå universitet,Institutionen för matematik och matematisk statistik

Markström, Klas, Docent (thesis advisor): Umeå universitet,Institutionen för matematik och matematisk statistik

Goddyn, Luis, Professor (opponent): Simon Fraser University, Burnaby, Canada

show less...

(creator_code:org_t)

ISBN 9789174593990
Umeå : Umeå universitet, 2012
English 69 s.
Series: Doctoral thesis / Umeå University, Department of Mathematics, 1102-8300 ; 53

Related links:: https://umu.diva-por... (primary) (Raw object); show more...; https://urn.kb.se/re...; show less...

Doctoral thesis (other academic/artistic)

Abstract Subject headings

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.

Subject headings

NATURVETENSKAP -- Matematik -- Diskret matematik (hsv//swe)
NATURAL SCIENCES -- Mathematics -- Discrete Mathematics (hsv//eng)

Keyword

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
Mathematics
matematik

Publication and Content Type

vet (subject category)
dok (subject category)

Find in a library

Snarks Generation, coverings and colourings (Search the publication in LIBRIS)

To the university's database

1 of 1
Previous record
Next record
To hitlist

Find more in SwePub

By the author/editor: Hägglund, Jonas, ...; Häggkvist, Rolan ...; Markström, Klas, ...; Goddyn, Luis, Pr ...

About the subject

NATURAL SCIENCES: NATURAL SCIENCES; and Mathematics; and Discrete Mathema ...

Parts in the series: Doctoral thesis ...

By the university: Umeå University

Search outside SwePub

Extend your search to:: Google; Google Book Search; Google Scholar

Kungliga biblioteket hanterar dina personuppgifter i enlighet med EU:s dataskyddsförordning (2018), GDPR. Läs mer om hur det funkar här.
Så här hanterar KB dina uppgifter vid användning av denna tjänst.

LIBRIS.kb.se