Snark i grafteorin är en sammankopplad kubisk graf utan broar med kromatiskt index 4. Det är med andra ord en graf där varje vertex har tre angränsande hörn och kanterna inte kan färgas med endast tre färger, så att två kanter av samma färg konvergerar inte vid en vertex. (Genom Vizings teorem är det kromatiska indexet för en kubisk graf 3 eller 4.) För att undvika triviala fall anses grafer med omkrets mindre än 5 ofta inte vara snarkar.
Man tror att trots den enkla definitionen och långa historiken av studier, är egenskaperna och strukturen hos snarks föga kända [1] .
Peter Tat blev först intresserad av snarks 1880 när han bevisade att fyrfärgssatsen motsvarar att säga att ingen snark är plan [2] . Den första kända snarken var greve Petersen , som hittades 1898 . År 1946 hittade den jugoslaviske matematikern Danilo Blanusha ytterligare två snarks, båda med 18 hörn, kallade Blanusha snarks [3] . Den fjärde snarken hittades två år senare av Tutt , som arbetade under pseudonymen Blanche Descartes , och det var en graf av storleksordningen 210 [4] [5] . 1973 hittade Szekeresh den femte snarken, Snarken of Szekeresh . [6] År 1975 generaliserade Isaacs Rufus Blalushis metod för att konstruera två oändliga familjer av snarks, Flowers och BDS (Blanushi-Descartes-Szekeres Snark), en familj som inkluderar två Blalushi-snarkar, Descartes' Snark och Szekeres ' Snark [7] . Isaacs upptäckte också en 30-uddig snark som inte tillhör BDS-familjen och inte är en blomma - en dubbelstjärna .
Termen "snark" myntades av Martin Gardner 1976 efter den svårfångade snarkvarelsen från Lewis Carrolls The Hunting of the Snark [8] .
Alla snarks är icke-hamiltonska , och många kända snarks är hypo -hamiltonska - att ta bort en enda vertex ger en Hamiltonsk subgraf. Hypohamiltoniska snarks måste vara bikritiska - att ta bort två valfria hörn ger en subgraf som kan kantfärgas med 3 färger. [9] [10]
Det har visat sig att antalet snarks för ett givet antal hörn begränsas av en exponentiell funktion [11] . (Som kubiska grafer måste alla snarks ha ett jämnt antal hörn.) OEIS -sekvensen A130315 innehåller antalet icke-triviala snarks med 2n hörn för små värden på n [12] .
Den dubbla cykeltäckningsförmodan anger att man i varje brolös graf kan hitta en uppsättning cykler som täcker varje kant två gånger, eller, på motsvarande sätt, att grafen kan bäddas in i en yta på ett sådant sätt att alla ytor är enkla cykler. Snarks utgör ett svårt fall för denna gissning - om det är sant för snarks, är det sant för alla grafer [13] . I detta avseende antog Branko Grünbaum att det är omöjligt att bädda in någon snark i en yta på ett sådant sätt att alla ytor är enkla cykler och dessutom, vilka två ytor som helst inte har gemensamma kanter eller har en gemensam kant. Martin Kohol fann dock ett motexempel till denna Grünbaums gissning [14] [15] [16] .
Tutt förmodade att någon snark har en Petersen-graf som moll . Således antog han att den minsta snark, Petersen-grafen, kan erhållas från vilken annan snark som helst genom att dra ihop vissa kanter och ta bort andra. Vilket är likvärdigt (eftersom Petersen-grafen har en maximal grad av tre) med påståendet att varje snark innehåller en subgraf som kan erhållas från Petersen-grafen genom att dividera några kanter. Denna gissning är en förstärkning av fyrfärgssatsen, eftersom varje graf som innehåller Petersen-grafen som moll inte kan vara plan. 1999 tillkännagav Robertson , Sanders , Seymour och Thomas beviset för gissningarna [17] , men från och med 2012 har beviset endast publicerats delvis [18] .
Tat föreslog också som en gissning ett generaliserat snark-teorem för godtyckliga grafer – varje brolös graf som inte har en Petersen-graf som moll har ett noll-4-flöde . Vilket innebär att kanterna på grafen kan ges riktningar och märkas med siffror från mängden {1, 2, 3} så att summan av de inkommande talen minus summan av de utgående talen vid varje vertex är delbar med fyra. Som Tutt visade finns en sådan tilldelning för kubiska grafer om och bara om kanterna kan färgas med tre färger, så i det här fallet följer gissningen av snarksatsen. Förmodan förblir dock öppen för andra (icke-kubiska) grafer [19] .
En lista över alla snarkar med 36 hörn, exklusive snarkar med 36 hörn och omkrets 4, skapades av Gunnar Brinkmann, Jan Gödgeber, Jonas Hägglund och Claes Markström 2012 [20] .