Snark en teoría de grafos es un grafo cúbico conexo sin puentes con índice cromático 4. En otras palabras, es un grafo en el que cada vértice tiene tres vértices vecinos y las aristas no se pueden colorear con solo tres colores, de modo que dos aristas del mismo color no convergen en un vértice. (Según el teorema de Vizing , el índice cromático de un gráfico cúbico es 3 o 4). Para evitar casos triviales, los gráficos con un perímetro inferior a 5 a menudo no se consideran snarks.
Se cree que, a pesar de la definición simple y la larga historia de estudio, las propiedades y la estructura de los snarks son poco conocidas [1] .
Peter Tat se interesó por primera vez en los snarks en 1880 cuando demostró que el teorema de los cuatro colores equivale a decir que ningún snark es plano [2] . El primer snark conocido fue el Conde Petersen , encontrado en 1898 . En 1946, el matemático yugoslavo Danilo Blanusha encontró dos snarks más, ambos con 18 vértices, llamados snarks Blanusha [3] . El cuarto snark fue encontrado dos años después por Tutt , trabajando bajo el seudónimo de Blanche Descartes , y era un grafo de orden 210 [4] [5] . En 1973, Szekeresh encontró el quinto snark, el Snark de Szekeresh . [6] En 1975, Isaacs Rufus generalizó el método de Blalushi para construir dos familias infinitas de snarks, Flowers y BDS (Blanushi-Descartes-Szekeres Snark), familia que incluye dos snarks de Blalushi, el Snark de Descartes y el Snark de Szekeres [7] . Isaacs también descubrió un snark de 30 puntas que no pertenece a la familia BDS y no es una flor, una estrella doble .
El término "snark" fue acuñado por Martin Gardner en 1976 después de la escurridiza criatura snark de The Hunting of the Snark de Lewis Carroll [8] .
Todos los snarks son no hamiltonianos , y muchos snarks conocidos son hipo -hamiltonianos; la eliminación de cualquier vértice da un subgrafo hamiltoniano. Los snarks hipohamiltonianos deben ser bicríticos : eliminar dos vértices cualesquiera da un subgrafo que se puede colorear con 3 colores. [9] [10]
Se ha demostrado que el número de snarks para un número dado de vértices está limitado por una función exponencial [11] . (Al ser gráficos cúbicos, todos los snarks deben tener un número par de vértices). La secuencia OEIS A130315 contiene el número de snarks no triviales con 2n vértices para valores pequeños de n [12] .
La conjetura de cobertura de doble ciclo establece que en cualquier gráfico sin puente se puede encontrar un conjunto de ciclos que cubren cada borde dos veces o, de manera equivalente, que el gráfico se puede incrustar en una superficie de tal manera que todas las caras sean ciclos simples. Los snarks constituyen un caso difícil para esta conjetura: si es cierto para los snarks, lo es para todos los gráficos [13] . A este respecto, Branko Grünbaum conjeturó que es imposible incrustar cualquier snark en una superficie de tal manera que todas las caras sean ciclos simples y, además, dos caras cualesquiera no tengan aristas comunes o tengan una arista común. Sin embargo, Martin Kohol encontró un contraejemplo a esta conjetura de Grünbaum [14] [15] [16] .
Tutt conjeturó que cualquier snark tiene un gráfico de Petersen como menor . Por lo tanto, conjeturó que el snark más pequeño, el gráfico de Petersen, se puede obtener de cualquier otro snark contrayendo algunos bordes y eliminando otros. Lo cual es equivalente (ya que el gráfico de Petersen tiene un grado máximo de tres) a la afirmación de que cualquier snark contiene un subgrafo que se puede obtener del gráfico de Petersen dividiendo algunas aristas. Esta conjetura es un refuerzo del teorema de los cuatro colores, ya que cualquier gráfico que contenga el gráfico de Petersen como menor no puede ser plano. En 1999, Robertson , Sanders , Seymour y Thomas anunciaron la prueba de la conjetura [17] , pero a partir de 2012 la prueba solo se ha publicado parcialmente [18] .
Tat también propuso como conjetura un teorema de snark generalizado para gráficos arbitrarios: cualquier gráfico sin puente que no tenga un gráfico de Petersen como menor tiene un flujo de 4 ceros en ninguna parte . Lo que significa que a los bordes del gráfico se les pueden dar direcciones y etiquetar con números del conjunto {1, 2, 3} para que la suma de los números entrantes menos la suma de los números salientes en cada vértice sea divisible por cuatro. Como mostró Tutt, tal asignación existe para gráficos cúbicos si y solo si los bordes se pueden colorear con tres colores, por lo que en este caso la conjetura se deriva del teorema de snark. Sin embargo, la conjetura permanece abierta para otros gráficos (no cúbicos) [19] .
Gunnar Brinkmann, Jan Gödgeber, Jonas Hägglund y Claes Markström crearon una lista de todos los snarks con 36 vértices, excluyendo los snarks con 36 vértices y circunferencia 4, en 2012 [20] .