Snarks
Eckhard Steffen
Princeton

Abstract: Snarks are cubic bridgeless graphs with chromatic index four. For some famous conjectures, e.g. Tutte's 5-flow conjecture or the Cycle Double Cover Conjecture, it is known that a possible minimal counterexample must be a snark. This talk deals with the following topics.

i) There are certain parameters measuring "how far away" a snark is from being edge 3-colorable. We discuss some of these parameters and relate them to each other.

ii) There is a long standing discussion about the reductions of snarks. This discussion is mainly motivated by the question about the intrinsic properties of cubic graphs which force them to be a snark and the search for a recursive procedure to construct all snarks (and only snarks) starting from a well defined set of base elements. Here we give an overview over recent developments in this field.

iii) Finally we give a sufficient condition for a snark having a nowhere-zero 5-flow.