A Snark a gráfelméletben egy 4- es kromatikus indexű összekapcsolt köbös gráf hidak nélkül . Más szóval ez egy gráf, amelyben minden csúcsnak három szomszédos csúcsa van, és az éleket nem lehet csak három színnel színezni, így ugyanannak a két éle a színek nem konvergálnak egy csúcsban. ( Vizing tétele szerint egy köbös gráf kromatikus indexe 3 vagy 4.) A triviális esetek elkerülése érdekében az 5-nél kisebb kerületű gráfokat gyakran nem tekintik snarknak .
Úgy gondolják, hogy az egyszerű meghatározás és a tanulmányok hosszú története ellenére a snarkok tulajdonságai és szerkezete kevéssé ismert [1] .
Peter Tat először 1880-ban kezdett érdeklődni a snarkok iránt, amikor bebizonyította, hogy a négyszín-tétel egyenértékű azzal, hogy azt mondjuk, hogy egyetlen snark sem síkbeli [2] . Az első ismert snark Petersen gróf volt, 1898 -ban találták meg . 1946- ban Danilo Blanusha jugoszláv matematikus további két snarkot talált, mindkettő 18 csúcsú, ezeket Blanusha snarknak nevezték [3] . A negyedik snarkot két évvel később találta meg a Blanche Descartes álnéven dolgozó Tutt , és ez egy 210-es rendű grafikon volt [4] [5] . 1973- ban Szekeresh megtalálta az ötödik snarkot, a Szekeresh Snarkot . [6] 1975 -ben Isaacs Rufus általánosította Blalushi módszerét, hogy két végtelen snarkot, a Flowers -t és a BDS-t (Blanushi-Descartes-Szekeres Snark) hozzon létre, amely család két Blalushi snarkot, Descartes Snarkot és Szekeres Snarkot tartalmaz [7] . Isaacs felfedezett egy 30 ágú snarkot is, amely nem tartozik a BDS családba, és nem virág – kettős csillag .
A "snark" kifejezést Martin Gardner alkotta meg 1976-ban, a megfoghatatlan snark lény után Lewis Carroll The Hunting of the Snark című művéből [ 8] .
Az összes snark nem Hamilton- féle , és sok ismert snark hipo -Hamilton- féle – egyetlen csúcs eltávolítása Hamilton részgráfot ad. A hipohamiltoni snarknak bickritikusnak kell lenniük – ha bármelyik két csúcsot eltávolítjuk, akkor egy részgráfot kapunk, amely 3 színnel élszínezhető. [9] [10]
Kimutatták, hogy egy adott számú csúcshoz tartozó snarkok számát egy exponenciális függvény korlátozza [11] . (Köbös gráfokról lévén szó, minden snarknak páros számú csúcsnak kell lennie.) Az OEIS A130315 sorozata tartalmazza a nem triviális snark számát 2n csúcstal kis n érték esetén [12] .
A kettős ciklus lefedettség sejtése kimondja, hogy bármely híd nélküli gráfban találhatunk olyan ciklushalmazt, amely minden élt kétszer fed le, vagy ezzel egyenértékű, hogy a gráf beágyazható egy felületbe úgy, hogy minden lap egyszerű ciklus. A snarkok nehéz esetet alkotnak ennek a sejtésnek – ha igaz a snarkra, akkor minden gráfra igaz [13] . Ezzel kapcsolatban Branko Grünbaum úgy sejtette, hogy lehetetlen úgy beágyazni egy felületbe, hogy minden lap egyszerű ciklus legyen, és ráadásul bármelyik két lapnak vagy nincs közös éle, vagy van egy közös éle. Martin Kohol azonban talált ellenpéldát erre a Grünbaum-sejtésre [14] [15] [16] .
Tutt úgy sejtette, hogy minden snarknak van egy Petersen-gráfja, mint kiskorú . Így azt sejtette, hogy a legkisebb snarkot, a Petersen-gráfot bármely más snarkból megkaphatjuk, ha egyes éleket összehúzunk, másokat pedig eltávolítunk. Ami ekvivalens (mivel a Petersen-gráf maximális foka három) azzal az állítással, hogy bármely snark tartalmaz egy részgráfot, amelyet a Petersen-gráfból néhány él elosztásával kaphatunk. Ez a sejtés a négy szín tétel erősítését jelenti, mivel a Petersen-gráfot mellékként tartalmazó gráf nem lehet síkbeli. 1999-ben Robertson , Sanders , Seymour és Thomas bejelentette a sejtés bizonyítását [17] , de 2012-től a bizonyítékot csak részben publikálták [18] .
Tat feltételezésként egy általánosított snark-tételt is javasolt tetszőleges gráfokhoz – minden olyan híd nélküli gráfnak, amely nem rendelkezik Petersen-gráfmal, mint kisebb, sehol nulla 4-es áramlással rendelkezik . Ami azt jelenti, hogy a gráf élei irányokat adhatnak, és az {1, 2, 3} halmazból származó számokkal címkézhetők úgy, hogy a bejövő számok összege mínusz a kimenő számok összege minden csúcsban osztható néggyel. Mint Tutt megmutatta, akkor és csak akkor létezik ilyen hozzárendelés a köbös gráfokhoz, ha az élek három színnel színezhetők, tehát ebben az esetben a sejtés a snark tételből következik. A sejtés azonban nyitva marad más (nem köbös) gráfok számára [19] .
Gunnar Brinkmann, Jan Gödgeber, Jonas Hägglund és Claes Markström 2012-ben készített egy listát az összes 36 csúcsú snarkról, kivéve a 36 csúcsú és 4-es kerületű snarkat [20] .