En teoría de grafos , una rama de las matemáticas , un snark es un grafo cúbico conectado , sin istmo y con un índice cromático igual a 4. En otras palabras, es un grafo en el que cada vértice tiene tres vecinos, y cuyas aristas no se pueden colorear. con solo 3 colores sin dos bordes del mismo color que se encuentran en el mismo 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, a menudo se requiere además que los snarks tengan una malla de al menos 5.
Los snarks fueron nombrados por el matemático estadounidense Martin Gardner en 1976, en honor al misterioso y esquivo objeto del poema de Lewis Carroll La caza del Snark .
Peter Guthrie Tait inició el estudio de los snarks en 1880, cuando demostró que demostrar el teorema de los cuatro colores equivalía a demostrar que cualquier gráfico cúbico plano podía tener sus bordes coloreados con tres colores. O en otras palabras, que ningún snark es plano .
El primer snark conocido fue el grafo de Petersen , descubierto en 1898. En 1946, el matemático croata Danilo Blanuša descubrió dos snarks más, ambos con 18 vértices, ahora llamados Blanuša snarks . El cuarto snark conocido fue descubierto dos años después por Bill Tutte, bajo el seudónimo de Blanche Descartes, y tenía 210 vértices. En 1973, George Szekeres descubrió el quinto snark conocido, el snark de Szekeres . En 1975, Rufus Isaacs generalizó el método Blanuša para construir dos familias infinitas de snarks: las flores snarks y las BDS o Blanuša-Descartes-Szekeres snarks, una familia que incluye los dos snarks de Blanuša, el snark de Descartes y Szekeres snark. Isaacs también descubrió un snark de 30 picos que no pertenece a la familia BDS y que no es un snark de flores: el snark de doble estrella .
Escribiendo en The Electronic Journal of Combinatorics, Miroslav Chladný afirma que “Al estudiar los muchos problemas importantes y difíciles en la teoría de grafos (como la conjetura de doble superposición y la conjetura de 5 flujos, nos encontramos con un tipo interesante de gráficos de algún tipo) . pequeños misteriosos llamados snarks. A pesar de su simple definición ... y después de más de un siglo de investigación, sus propiedades y estructura siguen siendo en gran parte desconocidas ".
Todos los snarks son no hamiltonianos y varios snarks conocidos son hipohamiltonianos : al eliminar cualquier vértice, el gráfico se vuelve hamiltoniano. Un snark hipohamiltoniano es necesariamente bicrítico : al eliminar cualquier par de vértices, los bordes del gráfico se pueden colorear con 3 colores.
Hemos podido demostrar que el número de snarks que tienen un número par dado de vértices se reduce mediante una función exponencial de este número de vértices (como los snarks son gráficos cúbicos, necesariamente tienen un número par de vértices). La secuencia A130315 del OEIS da el número de snarks no triviales con vértices para valores pequeños de : 0, 0, 0, 0, 1, 0, 0, 0, 2, 6, 20, 38, 280, 2900 , 28399, 293059, 3833587, 60167732.
La conjetura de la doble capa (in) establece que en cualquier gráfico sin istmo, se puede encontrar un conjunto de ciclos que pasan dos veces por cada borde. Una formulación equivalente es que el gráfico se puede sumergir (adentro) en una superficie tal que todas las caras sean ciclos de inmersión simples.
Los snarks son el caso difícil en esta conjetura: si es cierto para snarks, lo será para todos los gráficos.
En relación con este problema, Branko Grünbaum conjeturó que era imposible incrustar un gráfico en una superficie de modo que todas las caras sean ciclos simples y dos caras cualesquiera estén disjuntas o compartan un solo borde común. Esta conjetura resultó ser falsa, ya que Martin Kochol encontró un contraejemplo.
WT Tutte conjeturó que cada snark tiene el gráfico de Petersen como menor . En otras palabras, planteó la hipótesis de que el snark más pequeño, el gráfico de Petersen, podría obtenerse de cualquier otro snark contrayendo ciertos bordes y eliminando vértices o bordes aislados.
Una hipótesis equivalente es que cualquier snark puede formarse a partir del gráfico de Petersen subdividiendo algunos de sus bordes por homeomorfismo .
En 1999, Neil Robertson , Daniel Sanders , Paul Seymour y Robin Thomas anunciaron una demostración de la conjetura de Tutte. Sarah-Marie Belcastro, sin embargo, señala que en 2012, su manifestación permanece en gran parte inédita.
Tutte también emitió una conjetura generalizando el teorema de snark a gráficos arbitrarios: cualquier gráfico sin un istmo y sin un gráfico de Petersen como un flujo menor de cero en ninguna parte de tipo 4 (en) . Esto significa que a los bordes del gráfico se les puede asignar una orientación y un número igual a 1, 2 o 3, de modo que la suma de los números entrantes menos la suma de los números salientes sea divisible por 4 independientemente del vértice. Como mostró Tutte, para gráficos cúbicos tal asignación existe si y solo si los bordes se pueden colorear con 3 colores, por lo que la conjetura se sigue del teorema de snark en el caso de gráficos cúbicos. Sin embargo, la conjetura permanece abierta para los otros gráficos.
En 2012, Gunnar Brinkmann, Jan Goedgebeur, Jonas Hägglund y Klas Markström generaron todos los snarks hasta 36 vértices a través de una búsqueda por computadora.