View source for Snark (graph theory)

{{good article}}
{{Short description|3-regular graph with no 3-edge-coloring}}
{{About|a term in graph theory||Snark (disambiguation)}}

[[Image:Petersen1_tiny.svg|thumb|right|The [[Petersen graph]] is the smallest snark.]]
[[Image:Flower snarkv.svg|thumb|right|The [[flower snark]] J<sub>5</sub> is one of six snarks on 20 vertices.]]

In the [[mathematics|mathematical]] field of [[graph theory]], a '''snark''' is an [[undirected graph]] with [[cubic graph|exactly three edges per vertex]] whose [[edge coloring|edges cannot be colored]] with only three colors. In order to avoid trivial cases, snarks are often restricted to have additional requirements on their [[Connectivity (graph theory)|connectivity]] and on [[Girth (graph theory)|the length of their cycles]]. Infinitely many snarks exist.

One of the equivalent forms of the [[four color theorem]] is that every snark is a [[planar graph|non-planar graph]]. 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
{{cquote|In the study of various important and difficult problems in graph theory (such as the [[cycle double cover]] conjecture and the [[Nowhere-zero flow#Theory|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.{{r|chladny2010}}}}
As well as the problems they mention, [[W. T. Tutte]]'s ''snark conjecture'' concerns the existence of [[Petersen graph]]s as [[graph minor]]s of snarks; its proof has been long announced but remains unpublished, and would settle a special case of the existence of [[Nowhere-zero flows|nowhere zero 4-flows]].

==History and examples==
Snarks were so named by the American mathematician [[Martin Gardner]] in 1976, after the mysterious and elusive object of the poem ''[[The Hunting of the Snark]]'' by [[Lewis Carroll]].{{r|gardner}} However, the study of this class of graphs is significantly older than their name. [[Peter G. Tait]] initiated the study of snarks in 1880, when he proved that the [[four color theorem]] is equivalent to the statement that no snark is [[Planar graph|planar]].{{r|tait}}  The first graph known to be a snark was the [[Petersen graph]]; it was proved to be a snark by [[Julius Petersen]] in 1898,{{r|petersen}} although it had already been studied for a different purpose by [[Alfred Kempe]] in 1886.{{r|kempe}}

The next four known snarks were
*the [[Blanuša snarks]] (two with 18 vertices), discovered by [[Danilo Blanuša]] in 1946,{{r|blanusa}}
*the [[Descartes snark]] (210 vertices), discovered by [[Bill Tutte]] in 1948,{{r|descartes}} and
*the [[Szekeres snark]] (50 vertices), discovered by [[George Szekeres]] in 1973.{{r|szekeres}}
In 1975, [[Rufus Isaacs (game theorist)|Rufus Isaacs]] generalized Blanuša's method to construct two infinite families of snarks: the [[flower snark]]s and the Blanuša–Descartes–Szekeres snarks, a family that includes the two Blanuša snarks, the [[Descartes snark]] and the Szekeres snark. Isaacs also discovered a 30-vertex snark that does not belong to the Blanuša–Descartes–Szekeres family and that is not a flower snark: the [[double-star snark]].{{r|isaacs}} Another infinite family, the [[Loupekine snark]]s, was published by Isaacs in 1976, credited to F. Loupekine. It includes two 22-vertex snarks derived from the Petersen graph.{{r|karcam}}
The 50-vertex [[Watkins snark]] was discovered in 1989.{{r|watkins}}

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.{{r|tietze}} However, because it contains a triangle, it is not generally considered a snark. Under strict definitions of snarks, the smallest snarks are the Petersen graph and Blanuša snarks, followed by six different 20-vertex snarks.{{r|bghm}}

A list of all of the snarks up to 36 vertices (according to a strict definition), and up to 34 vertices (under a weaker definition), was generated by Gunnar Brinkmann, Jan Goedgebeur, Jonas Hägglund and Klas Markström in 2012.{{r|bghm}} The number of snarks for a given even number of vertices grows at least exponentially in the number of vertices.{{r|skupien}} (Because they have odd-degree vertices, all snarks must have an even number of vertices by the [[handshaking lemma]].){{r|oddness}} [[OEIS]] sequence {{OEIS link|A130315}} contains the number of non-trivial snarks of <math>2n</math> vertices for small values of <math>n</math>.<ref>{{cite OEIS|A130315|mode=cs2}}</ref>

==Definition==
The precise definition of snarks varies among authors,{{r|bghm|isaacs}} but generally refers to [[cubic graphs]] (having exactly three edges at each vertex) whose [[edge coloring|edges cannot be colored]] with only three colors. By [[Vizing's theorem]], the number of colors needed for the edges of a cubic graph is either three ("class one" graphs) or four ("class two" graphs), so snarks are cubic graphs of class two. However, in order to avoid cases where a snark is of class two for trivial reasons, or is constructed in a trivial way from smaller graphs, additional restrictions on connectivity and cycle lengths are often imposed. In particular:
*If a cubic graph has a [[Bridge (graph theory)|bridge]], an edge whose removal would disconnect it, then it cannot be of class one. By the [[handshaking lemma]], the subgraphs on either side of the bridge have an odd number of vertices each. Whichever of three colors is chosen for the bridge, their odd number of vertices prevents these subgraphs from being covered by cycles that alternate between the other two colors, as would be necessary in a 3-edge-coloring. For this reason, snarks are generally required to be bridgeless.{{r|gardner|isaacs}}
*A [[Loop (graph theory)|loop]] (an edge connecting a vertex to itself) cannot be colored without causing the same color to appear twice at that vertex, a violation of the usual requirements for graph edge coloring. Additionally, a cycle consisting of two vertices connected by two edges can always be replaced by a single edge connecting their two other neighbors, simplifying the graph without changing its three-edge-colorability. For these reasons, snarks are generally restricted to [[simple graph]]s, graphs without loops or multiple adjacencies.{{r|isaacs}}
*If a graph contains a triangle, then it can again be simplified without changing its three-edge-colorability, by contracting the three vertices of the triangle into a single vertex. Therefore, many definitions of snarks forbid triangles.{{r|isaacs}} However, although this requirement was also stated in Gardner's work giving the name "snark" to these graphs, Gardner lists [[Tietze's graph]], which contains a triangle, as being a snark.{{r|gardner}}
*If a graph contains a four-vertex cycle, it can be simplified in two different ways by removing two opposite edges of the cycle and replacing the resulting paths of degree-two vertices by single edges. It has a three-edge-coloring if and only if at least one of these simplifications does. Therefore, Isaacs requires a "nontrivial" cubic class-two graph to avoid four-vertex cycles,{{r|isaacs}} and other authors have followed suit in forbidding these cycles.{{r|bghm}} The requirement that a snark avoid cycles of length four or less can be summarized by stating that the [[Girth (graph theory)|girth]] of these graphs, the length of their shortest cycles, is at least five.
*More strongly, the definition used by {{harvtxt|Brinkmann|Goedgebeur|Hägglund|Markström|2012}} requires snarks to be cyclically 4-edge-connected. That means there can be no subset of three or fewer edges, the removal of which would disconnect the graph into two subgraphs each of which has at least one cycle. Brinkmann et al. define a snark to be a cubic and cyclically 4-edge-connected graph of girth five or more and class two; they define a "weak snark" to allow girth four.{{r|bghm}}
Although these definitions only consider constraints on the girth up to five, snarks with arbitrarily large girth exist.{{r|kochol1996}}

==Properties==
Work by Peter G. Tait established that the [[four-color theorem]] is true if and only if every snark is non-planar.{{r|tait}} This theorem states that every planar graph has a [[graph coloring]] of its the vertices with four colors, but Tait showed how to convert 4-vertex-colorings of [[maximal planar graph]]s into 3-edge-colorings of their [[dual graph]]s, which are cubic and planar, and vice versa. A planar snark would therefore necessarily be dual to a counterexample to the four-color theorem. Thus, the [[four color theorem#Proof by computer|subsequent proof of the four-color theorem]]{{r|4color}} also demonstrates that all snarks are non-planar.{{r|belcastro}}

All snarks are non-[[Hamiltonian graph|Hamiltonian]]: when a cubic graph has a Hamiltonian cycle, it is always possible to 3-color its edges, by using two colors in alternation for the cycle, and the third color for the remaining edges. However, many known snarks are close to being Hamiltonian, in the sense that they are [[hypohamiltonian graph]]s: the removal of any single vertex leaves a Hamiltonian subgraph. A hypohamiltonian snark must be ''bicritical'': the removal of any two vertices leaves a three-edge-colorable subgraph.{{r|steffen}} The ''oddness'' of a cubic graph is defined as the minimum number of odd cycles, in any system of cycles that covers each vertex once (a [[Graph factorization|2-factor]]). 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.{{r|oddness}}

The [[cycle double cover conjecture]] posits that in every bridgeless graph one can find a collection of cycles covering each edge twice, or equivalently that the graph can be [[graph embedding|embedded]] onto a surface in such a way that all faces of the embedding are simple cycles. When a cubic graph has a 3-edge-coloring, it has a cycle double cover consisting of the cycles formed by each pair of colors. Therefore, among cubic graphs, the snarks are the only possible counterexamples. More generally, snarks form the difficult case for this conjecture: if it is true for snarks, it is true for all graphs.{{r|jaeger}} In this connection, [[Branko Grünbaum]] conjectured that no snark could be embedded onto a surface in such a way that all faces are simple cycles and such that every two faces either are disjoint or share only a single edge; if any snark had such an embedding, its faces would form a cycle double cover. However, a counterexample to Grünbaum's conjecture was found by Martin Kochol.{{r|kochol2009}}

Determining whether a given cyclically 5-connected cubic graph is 3-edge-colorable is [[NP-complete]]. Therefore, determining whether a graph is a snark is [[co-NP-complete]].{{r|kochol2010}}

==Snark conjecture==
[[W. T. Tutte]] conjectured that every snark has the Petersen graph as a [[minor (graph theory)|minor]]. That is, he conjectured that the smallest snark, the Petersen graph, may be formed from any other snark by contracting some edges and deleting others. Equivalently (because the Petersen graph has maximum degree three) every snark has a subgraph that can be formed from the Petersen graph by [[homeomorphism (graph theory)|subdividing some of its edges]]. This conjecture is a strengthened form of the [[four color theorem]], because any graph containing the Petersen graph as a minor must be nonplanar. In 1999, [[Neil Robertson (mathematician)|Neil Robertson]], [[Daniel P. Sanders]], [[Paul Seymour (mathematician)|Paul Seymour]], and [[Robin Thomas (mathematician)|Robin Thomas]] announced a proof of this conjecture.{{r|thomas}} Steps towards this result have been published in 2016 and 2019,{{r|doublecross|rst2019}} but the complete proof remains unpublished.{{r|belcastro}} See the [[Hadwiger conjecture (graph theory)|Hadwiger conjecture]] for other problems and results relating graph coloring to graph minors.

Tutte also conjectured a generalization to arbitrary graphs: every bridgeless graph with no Petersen minor has a [[Nowhere-zero flows|nowhere zero 4-flow]]. That is, the edges of the graph may be assigned a direction, and a number from the set {1, 2, 3}, such that the sum of the incoming numbers minus the sum of the outgoing numbers at each vertex is divisible by four. As Tutte showed, for cubic graphs such an assignment exists if and only if the edges can be colored by three colors, so the conjecture would follow from the snark conjecture in this case. However, proving the snark conjecture would not settle the question of the existence of 4-flows for non-cubic graphs.{{r|garden}}

==References==
{{reflist|refs=

<ref name=4color>{{Citation |last1=Appel |first1=Kenneth |author1-link=Kenneth Appel|last2=Haken |first2=Wolfgang|author2-link= Wolfgang Haken |year=1989 |title=Every Planar Map is Four-Colorable |publisher=American Mathematical Society |place=Providence, RI |isbn = 0-8218-5103-9 | mr=1025335 | series=Contemporary Mathematics | volume=98 | others=With the collaboration of J. Koch. | doi=10.1090/conm/098|s2cid=8735627 |url=http://projecteuclid.org/euclid.bams/1183538218 }}</ref>

<ref name=belcastro>{{citation
 | last = belcastro | first = sarah-marie | author-link = Sarah-Marie Belcastro
 | doi = 10.4169/college.math.j.43.1.082
 | issue = 1
 | journal = [[The College Mathematics Journal]]
 | mr = 2875562
 | pages = 82–87
 | s2cid = 118189042
 | title = The continuing saga of snarks
 | volume = 43
 | year = 2012}}</ref>

<ref name=bghm>{{citation
 | last1 = Brinkmann | first1 = Gunnar
 | last2 = Goedgebeur | first2 = Jan
 | last3 = Hägglund | first3 = Jonas
 | last4 = Markström | first4 = Klas
 | arxiv = 1206.6690
 | doi = 10.1016/j.jctb.2013.05.001
 | issue = 4
 | journal = [[Journal of Combinatorial Theory, Series B]]
 | mr = 3071376
 | pages = 468–488
 | s2cid = 15284747
 | title = Generation and properties of snarks
 | volume = 103
 | year = 2012}}</ref>

<ref name=blanusa>{{citation
 | last = Blanuša | first = Danilo | author-link = Danilo Blanuša
 | journal = Glasnik Matematičko-Fizički i Astronomski
 | mr = 26310
 | pages = 31–42
 | series = Ser. II
 | title = Le problème des quatre couleurs
 | volume = 1
 | year = 1946}}</ref>

<ref name=chladny2010>{{citation
 | last1 = Chladný | first1 = Miroslav
 | last2 = Škoviera | first2 = Martin
 | doi = 10.37236/304 | doi-access = free
 | journal = [[Electronic Journal of Combinatorics]]
 | mr = 2595492
 | page = R32
 | title = Factorisation of snarks
 | volume = 17
 | year = 2010}}</ref>

<ref name=descartes>{{citation
 | last = Descartes | first = Blanche | author-link = Blanche Descartes
 | doi = 10.2307/3610702
 | journal = [[The Mathematical Gazette]]
 | mr = 0026309
 | pages = 67–69
 | title = Network-colourings
 | volume = 32
 | year = 1948| issue = 299 | jstor = 3610702 | s2cid = 250434686 }}</ref>

<ref name=doublecross>{{citation
 | last1 = Edwards | first1 = Katherine
 | last2 = Sanders | first2 = Daniel P.
 | last3 = Seymour | first3 = Paul | author3-link = Paul Seymour (mathematician)
 | last4 = Thomas | first4 = Robin | author4-link = Robin Thomas (mathematician)
 | doi = 10.1016/j.jctb.2015.12.006
 | journal = [[Journal of Combinatorial Theory, Series B]]
 | mr = 3486338
 | pages = 66–95
 | title = Three-edge-colouring doublecross cubic graphs
 | url = https://web.math.princeton.edu/~pds/papers/cubxx/paper.pdf
 | volume = 119
 | year = 2016| s2cid = 2656843
 }}</ref>

<ref name=garden>{{citation
 | last = DeVos | first = Matthew
 | date = March 7, 2007
 | title = 4-flow conjecture
 | url = https://garden.irmacs.sfu.ca/?q=op/4_flow_conjecture
 | work = Open Problem Garden}}</ref>

<ref name=gardner>{{citation
 | last = Gardner | first = Martin | author-link = Martin Gardner
 | bibcode = 1976SciAm.234d.126G
 | department = [[Mathematical Games]]
 | doi = 10.1038/scientificamerican0476-126
 | issue = 234
 | journal = Scientific American
 | jstor = 24950334
 | pages = 126–130
 | title = Snarks, boojums, and other conjectures related to the {{not a typo|four-color-map}} theorem
 | volume = 4
 | year = 1976}}</ref>

<ref name=isaacs>{{citation
 | last = Isaacs | first = Rufus | author-link = Rufus Isaacs (game theorist)
 | doi = 10.2307/2319844
 | issue = 3
 | journal = [[The American Mathematical Monthly]]
 | jstor = 2319844
 | pages = 221–239
 | title = Infinite families of non-trivial trivalent graphs which are not Tait-colorable
 | volume = 82
 | year = 1975}}</ref>

<ref name=jaeger>{{citation
 | last = Jaeger | first = François |author-link=François Jaeger (mathematician)
 | editor1-last = Alspach | editor1-first = B. R.
 | editor2-last = Godsil | editor2-first = C. D.
 | contribution = A survey of the cycle double cover conjecture
 | doi = 10.1016/S0304-0208(08)72993-1
 | pages = 1–12
 | series = North-Holland Mathematics Studies
 | title = Annals of Discrete Mathematics 27: Cycles in Graphs
 | volume = 27
 | year = 1985
 | isbn = 978-0-444-87803-8}}</ref>

<ref name=karcam>{{citation
 | last1 = Karam | first1 = Kaio
 | last2 = Campos | first2 = C. N.
 | doi = 10.1016/j.disc.2014.02.016
 | journal = Discrete Mathematics
 | mr = 3188983
 | pages = 20–28
 | title = Fulkerson's conjecture and Loupekine snarks
 | volume = 326
 | year = 2014| doi-access = free
 }}</ref>

<ref name=kempe>{{citation
 | last = Kempe | first = A. B. | author-link = Alfred Kempe
 | doi = 10.1098/rstl.1886.0002
 | journal = Philosophical Transactions of the Royal Society of London
 | pages = 1–70
 | title = A memoir on the theory of mathematical form
 | volume = 177
 | year = 1886| s2cid = 108716533 }}</ref>

<ref name=kochol1996>{{citation
 | last = Kochol | first = Martin
 | doi = 10.1006/jctb.1996.0032
 | issue = 1
 | journal = [[Journal of Combinatorial Theory, Series B]]
 | mr = 1385382
 | pages = 34–47
 | title = Snarks without small cycles
 | volume = 67
 | year = 1996| doi-access = free
 }}</ref>

<ref name=kochol2009>{{citation
 | last = Kochol | first = Martin
 | contribution = Polyhedral embeddings of snarks in orientable surfaces
 | pages = 1613–1619
 | volume = 137 
 | title = [[Proceedings of the American Mathematical Society]]
 | year = 2009}}</ref> 

<ref name=kochol2010>{{citation
 | last = Kochol | first = Martin
 | doi = 10.1016/j.dam.2010.06.019 | doi-access = free
 | issue = 16
 | journal = Discrete Applied Mathematics
 | mr = 2679785
 | pages = 1856–1860
 | title = Complexity of 3-edge-coloring in the class of cubic graphs with a polyhedral embedding in an orientable surface
 | volume = 158
 | year = 2010}}</ref>

<ref name=oddness>{{citation
 | last1 = Lukot'ka | first1 = Robert
 | last2 = Máčajová | first2 = Edita
 | last3 = Mazák | first3 = Ján
 | last4 = Škoviera | first4 = Martin
 | arxiv = 1212.3641
 | at = Paper 1.51
 | doi = 10.37236/3969
 | issue = 1
 | journal = [[Electronic Journal of Combinatorics]]
 | mr = 3336565
 | title = Small snarks with large oddness
 | volume = 22
 | year = 2015| s2cid = 4805178
 }}</ref>

<ref name=petersen>{{citation
 | last = Petersen | first = Julius | author-link = Julius Petersen
 | journal = [[L'Intermédiaire des Mathématiciens]]
 | pages = 225–227
 | title = Sur le théorème de Tait
 | url = https://archive.org/details/lintermdiairede03lemogoog/page/n239
 | volume = 5
 | year = 1898}}</ref>

<ref name=rst2019>{{citation
 | last1 = Robertson | first1 = Neil | author1-link = Neil Robertson (mathematician)
 | last2 = Seymour | first2 = Paul | author2-link = Paul Seymour (mathematician)
 | last3 = Thomas | first3 = Robin | author3-link = Robin Thomas (mathematician)
 | arxiv = 1403.2118
 | doi = 10.1016/j.jctb.2019.02.002
 | journal = [[Journal of Combinatorial Theory, Series B]]
 | mr = 3979232
 | pages = 219–285
 | title = Excluded minors in cubic graphs
 | volume = 138
 | year = 2019| s2cid = 16237685 }}</ref>

<ref name=skupien>{{citation
 | last = Skupień | first = Zdzisław|authorlink=Zdzisław Skupień
 | contribution = Exponentially many hypohamiltonian snarks
 | title = 6th Czech-Slovak International Symposium on Combinatorics, Graph Theory, Algorithms and Applications
 | series = Electronic Notes in Discrete Mathematics
 | volume = 28 | year = 2007 | pages = 417–424
 | doi = 10.1016/j.endm.2007.01.059}}</ref> 

<ref name=steffen>{{citation
 | last = Steffen | first = E.
 | title = Classification and characterizations of snarks
 | journal = [[Discrete Mathematics (journal)|Discrete Mathematics]]
 | volume = 188 | year = 1998 | issue = 1–3 | pages = 183–203
 | mr = 1630478 
 | doi = 10.1016/S0012-365X(97)00255-0| doi-access = free}}; {{citation
 | last = Steffen | first = E.
 | title = On bicritical snarks
 | journal = Math. Slovaca
 | volume = 51 | year = 2001 | issue = 2 | pages = 141–150
 | mr = 1841443 }}</ref>

<ref name=szekeres>{{citation
 | last = Szekeres | first = George | author-link = George Szekeres
 | doi = 10.1017/S0004972700042660 | doi-access = free
 | issue = 3
 | journal = Bulletin of the Australian Mathematical Society
 | pages = 367–387
 | title = Polyhedral decompositions of cubic graphs
 | volume = 8
 | year = 1973}}</ref>

<ref name=tait>{{citation
 | last = Tait | first = Peter Guthrie | author-link = Peter Guthrie Tait
 | doi = 10.1017/S0370164600044643
 | journal = Proceedings of the Royal Society of Edinburgh
 | page = 729
 | title = Remarks on the colourings of maps
 | volume = 10
 | year = 1880}}</ref>

<ref name=tietze>{{citation|first=Heinrich|last=Tietze|authorlink=Heinrich Franz Friedrich Tietze|url=https://sites.math.washington.edu/~mathcircle/circle/2014-15/advanced/mc-14a-w8.pdf|title=Einige Bemerkungen zum Problem des Kartenfärbens auf einseitigen Flächen|trans-title=Some remarks on the problem of map coloring on one-sided surfaces|journal=DMV Annual Report|volume=19|year=1910|pages=155–159}}</ref>

<ref name=thomas>{{citation
 | last = Thomas | first = Robin | author-link = Robin Thomas (mathematician)
 | contribution = Recent excluded minor theorems for graphs
 | contribution-url = https://people.math.gatech.edu/~thomas/PAP/bcc.pdf
 | pages = 201–222
 | publisher = Cambridge University Press
 | title = Surveys in Combinatorics, 1999
 | year = 1999}}</ref>

<ref name=watkins>{{citation
 | last = Watkins | first = John J.
 | editor1-last = Capobianco | editor1-first = Michael F.
 | editor2-last = Guan | editor2-first = Mei Gu | editor2-link = Meigu Guan
 | editor3-last = Hsu | editor3-first = D. Frank
 | editor4-last = Tian | editor4-first = Feng
 | contribution = Snarks
 | doi = 10.1111/j.1749-6632.1989.tb16441.x
 | location = New York
 | mr = 1110857
 | pages = 606–622
 | publisher = New York Academy of Sciences
 | series = Annals of the New York Academy of Sciences
 | title = Graph theory and its Applications: East and West, Proceedings of the First China–USA International Conference held in Jinan, June 9–20, 1986
 | volume = 576
 | year = 1989| s2cid = 222072657
 }}</ref>

}}

== External links ==
{{commons category}}
* {{MathWorld|title=Snark|urlname=Snark|mode=cs2}}

[[Category:Graph families]]
[[Category:Graph coloring]]
[[Category:Graph minor theory]]
[[Category:Regular graphs]]