Graafiteoriassa Snark on yhdistetty kuutiograafi ilman siltoja , joiden kromaattinen indeksi on 4. Toisin sanoen se on graafi , jossa jokaisessa kärjessä on kolme naapuripistettä ja reunoja ei voida värjätä vain kolmella värillä, joten saman kaksi reunaa värit eivät konvergoi yhteen kärkeen. ( Vizingin lauseen mukaan kuutiograafin kromaattinen indeksi on 3 tai 4.) Triviaalisten tapausten välttämiseksi kuvaajia, joiden ympärysmitta on alle 5, ei usein pidetä snarkeina.
Uskotaan, että yksinkertaisesta määritelmästä ja pitkästä tutkimushistoriasta huolimatta snarkien ominaisuudet ja rakenne ovat vähän tunnettuja [1] .
Peter Tat kiinnostui snarkeista ensimmäisen kerran vuonna 1880, kun hän osoitti, että neljän värin lause vastaa sanomista, ettei mikään snark ole tasomainen [2] . Ensimmäinen tunnettu snark oli kreivi Petersen , joka löydettiin vuonna 1898 . Vuonna 1946 jugoslavialainen matemaatikko Danilo Blanusha löysi kaksi muuta snarkia, molemmissa 18 kärkeä, joita kutsuttiin Blanusha-snarkeiksi [3] . Neljännen snarkin löysi kaksi vuotta myöhemmin Blanche Descartesin salanimellä työskennellyt Tutt , ja se oli 210:n kaavio [4] [5] . Vuonna 1973 Szekeresh löysi viidennen snarkin, Szekereshin snarkin . [6] Vuonna 1975 Isaacs Rufus yleisti Blalushin menetelmän rakentaa kaksi ääretöntä snarkkiperhettä, Flowers ja BDS (Blanushi-Descartes-Szekeres Snark), perhe, johon kuuluu kaksi Blalushi-snarkia, Descartesin Snark ja Szekeres Snark [7] . Isaacs löysi myös 30-kärkisen snarkin, joka ei kuulu BDS-perheeseen eikä ole kukka - kaksoistähti .
Termin "snark" keksi Martin Gardner vuonna 1976 Lewis Carrollin The Hunting of the Snarkin [ 8] -elokuvan jälkeen .
Kaikki snarkit ovat ei-Hamiltonin ja monet tunnetut snarkit ovat hypo - Hamiltonisia - minkä tahansa yksittäisen kärjen poistaminen antaa Hamiltonin aligraafin. Hypohamiltonin snarkkien tulee olla kaksinkertaisia - minkä tahansa kahden kärjen poistaminen antaa aligraafin, joka voidaan värjätä reunavärillä kolmella värillä. [9] [10]
On osoitettu, että snarkien lukumäärää tietylle määrälle pisteitä rajoittaa eksponentiaalinen funktio [11] . (Kuutiograafina kaikissa snarkeissa tulee olla parillinen määrä pisteitä.) OEIS -sekvenssi A130315 sisältää ei-triviaalien snarkien lukumäärän, joissa on 2n pistettä pienille n:n arvoille [ 12] .
Kaksoisjaksopeitto- oletus väittää, että mistä tahansa siltaattomasta graafista löytyy joukko jaksoja, jotka peittävät jokaisen reunan kahdesti, tai vastaavasti, että graafi voidaan upottaa pintaan siten, että kaikki pinnat ovat yksinkertaisia syklejä. Snarkit muodostavat vaikean tapauksen tälle olettamukselle - jos se on totta snarkeille, se on totta kaikille kaavioille [13] . Tässä suhteessa Branko Grünbaum arveli, että on mahdotonta upottaa mitään snarkia pintaan siten, että kaikki pinnat ovat yksinkertaisia jaksoja ja lisäksi millä tahansa kahdella pinnalla joko ei ole yhteisiä reunoja tai niillä on yksi yhteinen reuna. Martin Kohol löysi kuitenkin vastaesimerkin tälle Grünbaumin olettamukselle [14] [15] [16] .
Tutt arveli, että millä tahansa snarkilla on Petersenin graafi sivuaineena . Siten hän arveli, että pienin snark, Petersen-graafi, voidaan saada mistä tahansa muusta snarkista supistamalla joitain reunoja ja poistamalla toiset. Mikä vastaa (koska Petersen-graafin maksimiaste on kolme) väitettä, että mikä tahansa snark sisältää aligraafin, joka voidaan saada Petersen-graafista jakamalla joitain reunoja. Tämä olettamus on neljän värin lauseen vahvistus, koska mikään graafi, joka sisältää Petersenin graafin sivuaineena, ei voi olla tasomainen. Vuonna 1999 Robertson , Sanders , Seymour ja Thomas ilmoittivat arvelun todisteen [17] , mutta vuodesta 2012 lähtien todiste on julkaistu vain osittain [18] .
Tat ehdotti myös olettamukseksi yleistettyä snark-lausetta mielivaltaisille graafille – jokaisella siltaattomalla graafilla, jolla ei ole sivuaineena Petersen-graafia, on nollan 4-virtaus . Mikä tarkoittaa, että graafin reunoille voidaan antaa suunnat ja merkitä numerot joukosta {1, 2, 3} niin, että saapuvien lukujen summa miinus kunkin kärjen lähtevien lukujen summa on jaollinen neljällä. Kuten Tutt osoitti, tällainen osoitus on olemassa kuutiograafille, jos ja vain jos reunat voidaan värjätä kolmella värillä, joten tässä tapauksessa olettamus seuraa snark-lauseesta. Oletus jää kuitenkin avoimeksi muille (ei-kuutio) graafisille [19] .
Gunnar Brinkmann, Jan Gödgeber, Jonas Hägglund ja Claes Markström loivat luettelon kaikista 36 kärkeä sisältävistä snarkeista, lukuun ottamatta snarkeja, joissa on 36 kärkeä ja ympärysmitta 4, vuonna 2012 [20] .