Snark (graph theory)

Snark (graph theory)

In graph theory, a snark is a 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 three colors without two edges of the same color meeting at a point.

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. The first known snark was the Petersen graph, discovered in 1898. In 1946, Danilo Blanuša discovered two more snarks, and in 1975 Isaacs generalized Blanuša's method to construct an infinite family of snarks. 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.

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 (Steffen 1998, 2001).

nark 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 2001, Robertson, Sanders, Seymour, and Thomas announced a proof of this conjecture, and the result is now known as the snark theorem. [citation|last=Pegg|first=Ed, Jr.|authorlink=Ed Pegg, Jr.|title=Book Review: The Colossal Book of Mathematics|journal=Notices of the American Mathematical Society|volume=49|issue=9|year=2002|pages=1084–1086|url=http://www.ams.org/notices/200209/rev-pegg.pdf.] 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. [ [http://garden.irmacs.sfu.ca/?q=op/4_flow_conjecture 4-flow conjecture] , Open Problem Garden.]

List of snarks

*Petersen graph (10 vertices; 1898)
*Blanuša snarks (two with 18 vertices, discovered in 1946)
*Descartes' snark (discovered by Bill Tutte)
*Szekeres snark (50 vertices; 1973)
*flower snark (20 vertices)
*double star snark (30 vertices)

Notes

References

*
*
*
*citation
last = Steffen | first = E.
title = Classification and characterizations of snarks
journal = Discrete Mathematics
volume = 188 | year = 1998 | issue = 1–3 | pages = 183–203
id = MathSciNet | id = 1630478
doi = 10.1016/S0012-365X(97)00255-0
.
*citation
last = Steffen | first = E.
title = On bicritical snarks
journal = Math. Slovaca
volume = 51 | year = 2001 | issue = 2 | pages = 141–150
id = MathSciNet | id = 1841443
.
*

External links

*
* Alen Orbanić, Tomaž Pisanski, Milan Randić, and Brigite Servatius (preprint). " [http://www.ijp.si/ftp/pub/preprints/ps/2004/pp914.ps Blanuša Double] ". "Institute for Mathematics, Physics and Mechanics in Ljubljana, Slovenia".


Wikimedia Foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Look at other dictionaries:

  • List of graph theory topics — This is a list of graph theory topics, by Wikipedia page. See glossary of graph theory for basic terminology Contents 1 Examples and types of graphs 2 Graph coloring 3 Paths and cycles 4 …   Wikipedia

  • Minor (graph theory) — In graph theory, an undirected graph H is called a minor of the graph G if H is isomorphic to a graph that can be obtained by zero or more edge contractions on a subgraph of G. The theory of graph minors began with Wagner s theorem that a graph… …   Wikipedia

  • Snark — may refer to: *Snark (Lewis Carroll), a fictional animal in Lewis Carroll s The Hunting of the Snark (1876) *Jack London s yacht The Snark , described in the 1911 book The Cruise of the Snark *Snark (graph theory), a type of graph *SM 62 Snark,… …   Wikipedia

  • Hadwiger conjecture (graph theory) — In graph theory, the Hadwiger conjecture (or Hadwiger s conjecture) states that, if an undirected graph G requires k or more colors in any vertex coloring, then one can find k disjoint connected subgraphs of G such that each subgraph is connected …   Wikipedia

  • Petersen graph — Infobox graph name = Petersen graph image caption = The Petersen graph is most commonly drawn as a pentagon with a pentagram inside, with five spokes. namesake = Julius Petersen vertices = 10 edges = 15 radius = 2 diameter = 2 girth = 5 chromatic …   Wikipedia

  • Hypohamiltonian graph — In the mathematical field of graph theory, a graph G is said to be hypohamiltonian if G does not itself have a Hamiltonian cycle but every graph formed by removing a single vertex from G is Hamiltonian.HistoryHypohamiltonian graphs were first… …   Wikipedia

  • Cubic graph — Not to be confused with graphs of cubic functions. The Petersen graph is a Cubic graph …   Wikipedia

  • Double-star snark — The Double star snark Vertices 30 Edges 45 Chromatic number …   Wikipedia

  • Tietze's graph — The Tietze s graph Vertices 12 Edges 18 Diameter …   Wikipedia

  • Descartes snark — Image of a Descartes snark. Named after Blanche Descartes Vertices 210 Edges …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”