Snark i grafteori er en sammenhængende kubisk graf uden broer med kromatisk indeks 4. Det er med andre ord en graf, hvor hvert knudepunkt har tre nabospidser, og kanterne ikke kan farves med kun tre farver, således at to kanter af samme farve konvergerer ikke i et toppunkt. (Ved Vizings teorem er det kromatiske indeks for en kubisk graf 3 eller 4.) For at undgå trivielle tilfælde betragtes grafer med en omkreds på mindre end 5 ofte ikke som snert.
Det menes, at på trods af den enkle definition og lange historie af studier, er egenskaberne og strukturen af snarks lidt kendte [1] .
Peter Tat blev først interesseret i snarks i 1880, da han beviste, at firefarvesætningen svarer til at sige, at ingen snark er plan [2] . Den første kendte snark var grev Petersen , fundet i 1898 . I 1946 fandt den jugoslaviske matematiker Danilo Blanusha yderligere to snarks, begge med 18 hjørner, kaldet Blanusha snarks [3] . Den fjerde snark blev fundet to år senere af Tutt , der arbejdede under pseudonymet Blanche Descartes , og det var en graf af størrelsesorden 210 [4] [5] . I 1973 fandt Szekeresh den femte snark, Snark of Szekeresh . [6] I 1975 generaliserede Isaacs Rufus Blalushis metode til at konstruere to uendelige familier af snarks, Blomster og BDS (Blanushi-Descartes-Szekeres Snark), en familie, der omfatter to Blalushi-snarker, Descartes' Snark og Szekeres ' Snark [7] . Isaacs opdagede også en 30-takkede snark, der ikke tilhører BDS-familien og ikke er en blomst - en dobbeltstjerne .
Udtrykket "snark" blev opfundet af Martin Gardner i 1976 efter det undvigende snark - væsen fra Lewis Carrolls The Hunting of the Snark [8] .
Alle snarks er ikke-hamiltonske , og mange kendte snarks er hypo -hamiltonske - fjernelse af et enkelt toppunkt giver en Hamiltonsk subgraf. Hypohamiltonske snarks skal være bikritiske - fjernelse af to vilkårlige hjørner giver en undergraf, der kan kantfarves med 3 farver. [9] [10]
Det har vist sig, at antallet af snarks for et givet antal hjørner er begrænset af en eksponentiel funktion [11] . (Da er kubiske grafer, skal alle snarks have et lige antal hjørner.) OEIS -sekvensen A130315 indeholder antallet af ikke-trivielle snarks med 2n hjørner for små værdier på n [12] .
Formodningen om dobbeltcyklusdækning siger, at man i enhver broløs graf kan finde et sæt cyklusser, der dækker hver kant to gange, eller tilsvarende, at grafen kan indlejres i en overflade på en sådan måde, at alle flader er simple cyklusser. Snarks udgør en vanskelig sag for denne formodning - hvis det er sandt for snarks, er det sandt for alle grafer [13] . I denne forbindelse formodede Branko Grünbaum , at det er umuligt at indlejre nogen snark i en overflade på en sådan måde, at alle flader er simple cyklusser, og desuden har to flader enten ikke fælles kanter eller har en fælles kant. Martin Kohol fandt dog et modeksempel på denne Grünbaum-formodning [14] [15] [16] .
Tutt formodede, at enhver snark har en Petersen-graf som mol . Således formodede han, at den mindste snark, Petersen-grafen, kan fås fra enhver anden snark ved at trække nogle kanter sammen og fjerne andre. Hvilket svarer (da Petersen-grafen har en maksimal grad på tre) til udsagnet om, at enhver snark indeholder en subgraf, der kan hentes fra Petersen-grafen ved at dividere nogle kanter. Denne formodning er en styrkelse af firefarvesætningen, da enhver graf, der indeholder Petersen-grafen som et mol, ikke kan være plan. I 1999 annoncerede Robertson , Sanders , Seymour og Thomas beviset for formodningen [17] , men fra 2012 er beviset kun delvist offentliggjort [18] .
Tat foreslog også som en formodning et generaliseret snark-teorem for vilkårlige grafer - enhver broløs graf, der ikke har en Petersen-graf som mol, har en nowhere-nul 4-flow . Hvilket betyder, at grafens kanter kan gives retninger og mærkes med tal fra mængden {1, 2, 3}, således at summen af de indgående tal minus summen af de udgående tal ved hvert toppunkt er delelig med fire. Som Tutt viste, eksisterer en sådan tildeling for kubiske grafer, hvis og kun hvis kanterne kan farves med tre farver, så i dette tilfælde følger formodningen af snark-sætningen. Formodningen forbliver dog åben for andre (ikke-kubiske) grafer [19] .
En liste over alle snarks med 36 toppunkter, undtagen snarks med 36 toppunkter og omkreds 4, blev lavet af Gunnar Brinkmann, Jan Gödgeber, Jonas Hägglund og Claes Markström i 2012 [20] .