Snark (graph theory)

In the mathematical field of graph theory, a snark is a simple, connected, bridgeless cubic graph with chromatic index equal to 4. In other words, it is a graph in which every vertex has three neighbors, the connectivity is redundant so that removing no one edge would split the graph, and the edges cannot be colored by only three colors without two edges of the same color meeting at a point. (By Vizing's theorem, the chromatic index of a cubic graph is 3 or 4.) In order to avoid trivial cases, snarks are often restricted to have girth at least 5.

The Petersen graph is the smallest snark.
The flower snark J5 is one of six snarks on 20 vertices.

Writing in The Electronic Journal of Combinatorics, Miroslav Chladný states 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]

History

Peter Guthrie 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.[2] The first known snark was the Petersen graph, discovered in 1898. In 1946, Croatian mathematician Danilo Blanuša discovered two more snarks, both on 18 vertices, now named the Blanuša snarks.[3] The fourth known snark was found two years later by W. T. Tutte under the pseudonym Blanche Descartes; it has order 210.[4][5] In 1973, George Szekeres found the fifth known snark — the Szekeres snark.[6] In 1975, Rufus Isaacs generalized Blanuša's method to construct two infinite families of snarks: the flower snark and the BDS or Blanuša–Descartes–Szekeres snark, a family that includes the two Blanuša snarks, the Descartes snark and the Szekeres snark.[7] Isaacs also discovered a 30-vertices snark that does not belong to the BDS family and that is not a flower snark: the double-star snark.

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.[8]

Properties

All snarks are non-Hamiltonian, and many known snarks are hypohamiltonian: the removal of any single vertex leaves a Hamiltonian subgraph. A hypohamiltonian snark must be bicritical: the removal of any two vertices leaves a 3-edge-colorable subgraph.[9][10]

It has been shown that the number of snarks for a given even number of vertices is bounded below by an exponential function.[11] (Being cubic graphs, all snarks must have an even number of vertices.) OEIS sequence A130315 contains the number of non-trivial snarks of 2n vertices for small values of n.

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 embedded onto a surface in such a way that all faces of the embedding are simple cycles. Snarks form the difficult case for this conjecture: if it is true for snarks, it is true for all graphs.[12] In this connection, Branko Grünbaum conjectured that it was not possible to embed any snark 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; however, a counterexample to Grünbaum's conjecture was found by Martin Kochol.[13][14][15]

Work by Peter Tait established that the 4-color theorem is true if and only every snark is non-planar. Thus all snarks are non-planar.

Snark conjecture

W. T. Tutte conjectured that every snark has the Petersen graph as a 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 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, Daniel P. Sanders, Paul Seymour, and Robin Thomas announced a proof of this conjecture.[16] As of 2020, their proof remains largely unpublished.[17] See the Hadwiger conjecture for other problems and results relating graph coloring to graph minors.

Tutte also conjectured a generalization of the snark theorem to arbitrary graphs: every bridgeless graph with no Petersen minor has a 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 follows from the snark theorem in this case. However, this conjecture remains open for non-cubic graphs.[18]

List of snarks

A list of all of the snarks up to 36 vertices, except those with 36 vertices and girth 4, was generated by Gunnar Brinkmann, Jan Goedgebeur, Jonas Hägglund and Klas Markström in 2012.[19]

gollark: > I'm sleep deprived, maybe drunk, and feel like shit<@263493613860814848> try not being drunk and/or sleep deprived™
gollark: Bees flowing like honey.
gollark: ++magic py import randomrandom.randint(0, 1294127894712)
gollark: Also, identifiers are *exactly* 8 alphanumeric characters.
gollark: You can use underscores if you really must separate tokens.

References
  1. Chladný, Miroslav; Škoviera, Martin (2010), "Factorisation of snarks", The Electronic Journal of Combinatorics, 17: R32.
  2. Tait, Peter Guthrie (1880), "Remarks on the colourings of maps", Proceedings of the Royal Society of Edinburgh, 10: 729
  3. Blanuša, Danilo (1946), "Problem četiriju boja", Glasnik Mat. Fiz. Astr. Ser II, 1: 31–42
  4. Blanche Descartes, Network-colourings, The Mathematical Gazette (London) 32, 67-69, 1948.
  5. Martin Gardner, The Last Recreations: Hydras, Eggs, and Other Mathematical Mystifications, Springer, 2007, ISBN 0-387-25827-2, ISBN 978-0-387-25827-0
  6. Szekeres, George (1973), "Polyhedral decompositions of cubic graphs", Bulletin of the Australian Mathematical Society, 8 (3): 367–387, doi:10.1017/S0004972700042660.
  7. Isaacs, R. (1975), "Infinite families of non-trivial trivalent graphs which are not Tait-colorable", American Mathematical Monthly, 82 (3): 221–239, doi:10.2307/2319844, JSTOR 2319844
  8. Gardner, Martin (1976), "Mathematical Games", Scientific American, 4 (234): 126–130
  9. Steffen, E. (1998), "Classification and characterizations of snarks", Discrete Mathematics, 188 (1–3): 183–203, doi:10.1016/S0012-365X(97)00255-0, MR 1630478
  10. Steffen, E. (2001), "On bicritical snarks", Math. Slovaca, 51 (2): 141–150, MR 1841443
  11. Skupień, Zdzisław (2007). "Exponentially many hypohamiltonian snarks". Electronic Notes in Discrete Mathematics. 6th Czech-Slovak International Symposium on Combinatorics, Graph Theory, Algorithms and Applications. 28. pp. 417–424. doi:10.1016/j.endm.2007.01.059.
  12. Jaeger, François (1985), "A survey of the cycle double cover conjecture", Annals of Discrete Mathematics 27 – Cycles in Graphs, North-Holland Mathematics Studies, 27, pp. 1–12, doi:10.1016/S0304-0208(08)72993-1, ISBN 978-0-444-87803-8.
  13. Kochol, Martin (1996), "Snarks without small cycles", Journal of Combinatorial Theory, Series B, 67, pp. 34–47.
  14. Kochol, Martin (2009), "3-Regular non 3-edge-colorable graphs with polyhedral embeddings in orientable surfaces", Graph Drawing 2008, Editors: I.G. Tollis, M. Patrignani, Lecture Notes in Computer Science, 5417, pp. 319–323.
  15. Kochol, Martin (2009), "Polyhedral embeddings of snarks in orientable surfaces", Proceedings of the American Mathematical Society, 137, pp. 1613–1619.
  16. Thomas, Robin (1999). "Recent Excluded Minor Theorems for Graphs". Surveys in Combinatorics, 1999 (PDF). Cambridge University Press. pp. 201–222.
  17. belcastro, sarah-marie (2012), "The continuing saga of snarks", The College Mathematics Journal, 43 (1): 82–87, doi:10.4169/college.math.j.43.1.082, MR 2875562.
  18. "4-flow conjecture"., Open Problem Garden.
  19. Brinkmann, Gunnar; Goedgebeur, Jan; Hägglund, Jonas; Markström, Klas (2012), Generation and Properties of Snarks, arXiv:1206.6690, Bibcode:2012arXiv1206.6690B
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.