The Cycle Double Cover Conjecture and the Hunting of the Snark
Presented by Mr. Jonas HäGGLUND
Type: Oral presentation
Track: General session
It is well known that some classic conjectures in graph theory such as the Cycle Double Cover Conjecture (CDCC) and Tutte's 5-flow conjecture can be reduced to a certain family of cubic graphs called snarks, named after the elusive creature in Lewis Carroll's poem ''The hunting of the Snark''. By using improved search methods and very big computers we have now generated (caught) all snarks on 36 vertices and less. We tested these snarks for various properties and, among other things, verified some of the strongest versions of the CDCC for snarks of these orders. We were also able to prove that every cubic graph $G$ with a cycle of length at least $|V(G)|-10$ has a cycle double cover. Furthermore we found counterexamples to no less than eight conjectures on cycle covers and cycle decompositions.