Seminár z teórie grafov - Jan Goedgebeur (3.3.2016)

vo štvrtok 3.3.2016 o 9:50 hod. v posluchárni C

29. 02. 2016 10.54 hod.
Od: Martin Škoviera

Prednášajúci: Jan Goedgebeur (Ghent University, Belgium)

Názov prednášky: Generation of cubic graphs and snarks

Termín: 3.3.2016, 9:50 hod., poslucháreň C

Abstract:
In this talk we will present a new algorithm for the efficient generation of all non-isomorphic cubic graphs. We will also show how this algorithm can be extended for the efficient generation of all non-isomorphic snarks.
Snarks are of interest since for a lot of interesting open conjectures it can be proven that if the conjecture is false, the smallest possible counterexamples will be snarks.
Our implementation of this algorithm to generate snarks is more than 30 times faster than former generators for snarks. Using this generator we were able to generate all snarks up to 36 vertices. The new list of snarks allowed us to find counterexamples for several published open conjectures.