19-25 June 2011
Bled, Slovenia
Europe/Ljubljana timezone
Home > Timetable > Contribution details

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.


Location: Bled, Slovenia
Address: Best Western Hotel Kompas Bled

Primary authors