Snark v teorii grafů je souvislý kubický graf bez můstků s chromatickým indexem 4. Jinými slovy je to graf, ve kterém má každý vrchol tři sousední vrcholy a hrany nelze obarvit pouze třemi barvami, takže dvě hrany téhož barvy se nesbíhají v jednom vrcholu. (Podle Vizingova teorému je chromatický index kubického grafu 3 nebo 4.) Aby se předešlo triviálním případům, grafy s obvodem menším než 5 se často nepovažují za snarks.
Má se za to, že navzdory jednoduché definici a dlouhé historii studia jsou vlastnosti a struktura snarků málo známé [1] .
Peter Tat se poprvé začal zajímat o snarks v roce 1880, kdy dokázal, že věta o čtyřech barvách je ekvivalentní tvrzení, že žádný snark není rovinný [2] . První známý snark byl hrabě Petersen , nalezený v roce 1898 . V roce 1946 našel jugoslávský matematik Danilo Blanusha další dva snarky, oba s 18 vrcholy, nazývané Blanusha snarky [3] . Čtvrtý snark byl nalezen o dva roky později Tutt , pracující pod pseudonymem Blanche Descartes , a byl to graf řádu 210 [4] [5] . V roce 1973 našel Szekeresh pátého hada, Snark of Szekeresh . [6] V roce 1975 Isaacs Rufus zobecnil Blalushiho metodu ke konstrukci dvou nekonečných rodin snarků, Flowers a BDS (Blanushi-Descartes-Szekeres Snark), rodiny, která zahrnuje dva Blalushi snarks, Descartes' Snark a Szekeres ' Snark [7] . Isaacs také objevil 30cípého hada, který nepatří do rodiny BDS a není květinou – dvojitou hvězdou .
Termín „snark“ zavedl Martin Gardner v roce 1976 po nepolapitelném snark zvířeti z Lewise Carrolla The Hunting of the Snark [8] .
Všechny snarks jsou nehamiltonské a mnoho známých snarků je hypo - hamiltonských - odstraněním jakéhokoli jednotlivého vrcholu vznikne hamiltonovský podgraf. Hypohamiltonské snarks musí být bikritické – odstraněním libovolných dvou vrcholů vznikne podgraf, který může být obarven 3 barvami. [9] [10]
Ukázalo se, že počet snarků pro daný počet vrcholů je omezen exponenciální funkcí [11] . (Vzhledem k kubickému grafu musí mít všechny snarks sudý počet vrcholů.) OEIS sekvence A130315 obsahuje počet netriviálních snarků s 2n vrcholy pro malé hodnoty n [12] .
Dohad pokrytí dvojitým cyklem říká, že v jakémkoli bezmůstkovém grafu lze najít sadu cyklů pokrývajících každou hranu dvakrát, nebo ekvivalentně, že graf lze vložit do povrchu takovým způsobem, že všechny plochy jsou jednoduché cykly. Snarks tvoří obtížný případ pro tuto domněnku - pokud to platí pro snarky, platí to pro všechny grafy [13] . Branko Grünbaum se v tomto ohledu domníval, že je nemožné vložit do plochy jakýkoli snark tak, že všechny plochy jsou jednoduché cykly a navíc libovolné dvě plochy buď nemají společné hrany, nebo mají jednu společnou hranu. Martin Kohol však našel protipříklad k této Grünbaumově domněnce [14] [15] [16] .
Tutt se domníval, že každý snark má Petersenův graf jako menší . Domníval se tedy, že nejmenší snark, Petersenův graf, lze získat z jakéhokoli jiného snaru stažením některých hran a odstraněním jiných. Což je ekvivalentní (protože Petersenův graf má maximálně tři stupně) tvrzení, že jakýkoli snark obsahuje podgraf, který lze získat z Petersenova grafu dělením některých hran. Tato domněnka je posílením teorému o čtyřech barvách, protože žádný graf obsahující Petersenův graf jako menší nemůže být rovinný. V roce 1999 Robertson , Sanders , Seymour a Thomas oznámili důkaz domněnky [17] , ale od roku 2012 byl důkaz publikován pouze částečně [18] .
Tat také navrhl jako domněnku zobecněný teorém snark pro libovolné grafy – jakýkoli bezmůstkový graf, který nemá Petersenův graf jako vedlejší, má nikde nulový 4-tok . Což znamená, že hranám grafu lze dát směr a označit je čísly z množiny {1, 2, 3} tak, že součet příchozích čísel mínus součet odchozích čísel v každém vrcholu je dělitelný čtyřmi. Jak ukázal Tutt, takové zadání pro kubické grafy existuje právě tehdy, pokud lze hrany obarvit třemi barvami, takže v tomto případě dohad vyplývá z věty snark. Dohad však zůstává otevřený pro další (nekubické) grafy [19] .
Seznam všech snarků s 36 vrcholy, s výjimkou snarků s 36 vrcholy a obvodem 4, vytvořili Gunnar Brinkmann, Jan Gödgeber, Jonas Hägglund a Claes Markström v roce 2012 [20] .