Snark (teoría de grafos)

En el campo matemático de la teoría de grafos, un snark es un grafo no dirigido con exactamente tres aristas por vértice cuyas aristas no pueden colorearse con sólo tres colores.

[11]​ Sin embargo, debido a que contiene un triángulo, generalmente no se considera un snark.

[15]​ La definición precisa de snarks varía según los autores,[9]​[12]​ pero generalmente se refiere a grafos cúbicos (que tienen exactamente tres aristas en cada vértice) cuyas aristas no pueden colorearse con sólo tres colores.

Por tanto, un snark plano sería necesariamente dual a un contraejemplo del teorema de los cuatro colores.

[17]​ Así, la prueba posterior del teorema de los cuatro colores también demuestra que todos los snarks no son planares.

Por la misma razón por la que no tienen ciclos hamiltonianos, los snarks tienen imparidad positiva: un 2-factor completamente par llevaría a una coloración de 3 aristas, y viceversa.

[20]​ En este sentido, Branko Grünbaum conjeturó que ningún snark podría incrustarse en una superficie de forma que todas las caras fueran ciclos simples y que cada dos caras fueran disjuntas o compartieran una única arista; si algún snark tuviera tal incrustación, sus caras formarían una doble cubierta de ciclos.

Sin embargo, Martin Kochol encontró un contraejemplo a la conjetura de Grünbaum.

[21]​ Determinar si un grafo cúbico de 5 conexiones cíclicas es coloreable por 3 aristas es NP-completo.

[22]​ W. T. Tutte conjeturó que cada snark tiene el grafo de Petersen como menor.

En 1999, Neil Robertson, Daniel P. Sanders, Paul Seymour, y Robin Thomas anunciaron una prueba de esta conjetura.

Como demostró Tutte, para grafos cúbicos existe tal asignación si y sólo si las aristas se pueden colorear con tres colores, por lo que la conjetura se derivaría de la conjetura snark en este caso.