Snark (graph theory)

In order to avoid trivial cases, snarks are often restricted to have additional requirements on their connectivity and on the length of their cycles.

Research on snarks originated in Peter G. Tait's work on the four color theorem in 1880, but their name is much newer, given to them by Martin Gardner in 1976.

Beyond coloring, snarks also have connections to other hard problems in graph theory: writing in the Electronic Journal of Combinatorics, Miroslav Chladný and Martin Škoviera state that In the study of various important and difficult problems in graph theory (such as the cycle double cover conjecture and the 5-flow conjecture), one encounters an interesting but somewhat mysterious variety of graphs called snarks.

In spite of their simple definition...and over a century long investigation, their properties and structure are largely unknown.

[1]As well as the problems they mention, W. T. Tutte's snark conjecture concerns the existence of Petersen graphs as graph minors of snarks; its proof has been long announced but remains unpublished, and would settle a special case of the existence of nowhere zero 4-flows.

[11] Another notable cubic non-three-edge-colorable graph is Tietze's graph, with 12 vertices; as Heinrich Franz Friedrich Tietze discovered in 1910, it forms the boundary of a subdivision of the Möbius strip requiring six colors.

[17] Work by Peter G. Tait established that the four-color theorem is true if and only if every snark is non-planar.

A hypohamiltonian snark must be bicritical: the removal of any two vertices leaves a three-edge-colorable subgraph.

For the same reason that they have no Hamiltonian cycles, snarks have positive oddness: a completely even 2-factor would lead to a 3-edge-coloring, and vice versa.

It is possible to construct infinite families of snarks whose oddness grows linearly with their numbers of vertices.

In 1999, Neil Robertson, Daniel P. Sanders, Paul Seymour, and Robin Thomas announced a proof of this conjecture.

However, proving the snark conjecture would not settle the question of the existence of 4-flows for non-cubic graphs.