Snark

Материал из WEGA
Версия от 17:47, 23 июня 2011; Glk (обсуждение | вклад) (Новая страница: «'''Snark''' --- снарк. A '''snark''' is a ''connected'', ''bridgeless'' ''cubic'' graph with ''chromatic index'' equal to 4. P. G. Tait initiated the study o…»)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)
Перейти к навигации Перейти к поиску

Snark --- снарк.

A snark is a connected, bridgeless cubic graph with chromatic index equal to 4.

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

In 2001, Robertson, Sanders, Seymour, and Thomas announced a proof of W. T. Tutte's conjecture that every snark has the Petersen graph as a minor.