Snark (graph theory)

This article is about a term in graph theory. For other uses, see Snark (disambiguation).
The flower snark J5 is one of six snarks on 20 vertices.

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, 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.

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

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

Snark theorem

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, Robertson, Sanders, Seymour, and Thomas announced a proof of this conjecture.[16] As of 2012, 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 graphs that need not be cubic.[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]

References

  1. ↑ Chladný, Miroslav; Škoviera, Martin (2010), "Factorisation of snarks", The Electronic Journal of Combinatorics, 17: R32.
  2. ↑ Tait, P. G. (1880), "Remarks on the colourings of maps", Proc. R. Soc. 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, G. (1973), "Polyhedral decompositions of cubic graphs", Bull. Austral. Math. Soc., 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ń, Z. (2007), "6th Czech-Slovak International Symposium on Combinatorics, Graph Theory, Algorithms and Applications", Electronic Notes in Discrete Mathematics, 28: 417–424, doi:10.1016/j.endm.2007.01.059 |contribution= ignored (help)
  12. ↑ Jaeger, F. (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. ↑ Gunnar Brinkmann, Jan Goedgebeur, Jonas Hägglund and Klas Markström (2012), Generation and Properties of Snarks, arXiv:1206.6690Freely accessible

External links

This article is issued from Wikipedia - version of the 10/16/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.