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 se pueden colorear con solo tres colores. Para evitar casos triviales, los snarks suelen estar restringidos a tener requisitos adicionales en su conectividad y en la longitud de sus ciclos . Existen infinitos snarks.
Una de las formas equivalentes del teorema de los cuatro colores es que cada snark es un grafo no plano . La investigación sobre los snarks se originó en el trabajo de Peter G. Tait sobre el teorema de los cuatro colores en 1880, pero su nombre es mucho más reciente, dado por Martin Gardner en 1976. Más allá de la coloración, los snarks también tienen conexiones con otros problemas difíciles en la teoría de grafos: escribiendo en el Electronic Journal of Combinatorics , Miroslav Chladný y Martin Škoviera afirman que
En el estudio de diversos problemas importantes y difíciles de la teoría de grafos (como la conjetura de doble recubrimiento cíclico y la conjetura de flujo 5 ), uno se encuentra con una variedad interesante pero algo misteriosa de grafos llamados snarks. A pesar de su definición simple... y de más de un siglo de investigación, sus propiedades y estructura son en gran parte desconocidas. [1]
Además de los problemas que mencionan, la conjetura de snark de WT Tutte se refiere a la existencia de grafos de Petersen como grafos menores de snarks; su prueba ha sido anunciada hace tiempo pero permanece sin publicar, y resolvería un caso especial de existencia de 4-flujos con cero en ninguna parte .
Los snarks fueron denominados así por el matemático estadounidense Martin Gardner en 1976, en honor al misterioso y elusivo objeto del poema The Hunting of the Snark de Lewis Carroll . [2] Sin embargo, el estudio de esta clase de grafos es significativamente más antiguo que su nombre. Peter G. Tait inició el estudio de los snarks en 1880, cuando demostró que el teorema de los cuatro colores es equivalente a la afirmación de que ningún snark es plano . [3] El primer grafo conocido como snark fue el grafo de Petersen ; Julius Petersen demostró que era un snark en 1898, [4] aunque Alfred Kempe ya lo había estudiado con un propósito diferente en 1886. [5]
Los siguientes cuatro snarks conocidos fueron
En 1975, Rufus Isaacs generalizó el método de Blanuša para construir dos familias infinitas de snarks: los snarks de flores y los snarks de Blanuša–Descartes–Szekeres, una familia que incluye los dos snarks de Blanuša, el snark de Descartes y el snark de Szekeres. Isaacs también descubrió un snark de 30 vértices que no pertenece a la familia Blanuša–Descartes–Szekeres y que no es un snark de flores: el snark de doble estrella . [9] El snark de Watkins de 50 vértices fue descubierto en 1989. [10]
Otro grafo cúbico notable que no se puede colorear con tres aristas es el grafo de Tietze , con 12 vértices; como descubrió Heinrich Franz Friedrich Tietze en 1910, forma el límite de una subdivisión de la banda de Möbius que requiere seis colores. [11] Sin embargo, debido a que contiene un triángulo, generalmente no se lo considera un snark. Según las definiciones estrictas de snarks, los snarks más pequeños son el grafo de Petersen y los snarks de Blanuša, seguidos de seis snarks diferentes de 20 vértices. [12]
Gunnar Brinkmann, Jan Goedgebeur, Jonas Hägglund y Klas Markström generaron una lista de todos los snarks de hasta 36 vértices (según una definición estricta) y de hasta 34 vértices (según una definición más débil) en 2012. [12] El número de snarks para un número par dado de vértices crece al menos exponencialmente en el número de vértices. [13] (Debido a que tienen vértices de grado impar, todos los snarks deben tener un número par de vértices por el lema de handshaking ). [14] La secuencia OEIS A130315 contiene el número de snarks no triviales de vértices para valores pequeños de . [15]
La definición precisa de snarks varía entre los autores, [12] [9] pero generalmente se refiere a grafos cúbicos (que tienen exactamente tres aristas en cada vértice) cuyas aristas no se pueden colorear con solo tres colores. Según el teorema de Vizing , la cantidad de colores necesarios para las aristas de un grafo cúbico es tres (grafos "clase uno") o cuatro (grafos "clase dos"), por lo que los snarks son grafos cúbicos de clase dos. Sin embargo, para evitar casos en los que un snark es de clase dos por razones triviales, o se construye de manera trivial a partir de grafos más pequeños, a menudo se imponen restricciones adicionales sobre la conectividad y las longitudes de ciclo. En particular:
Aunque estas definiciones sólo consideran restricciones de circunferencia hasta cinco, existen snarks con circunferencias arbitrariamente grandes. [16]
El trabajo de Peter G. Tait estableció que el teorema de los cuatro colores es verdadero si y solo si cada snark es no plano. [3] Este teorema establece que cada grafo plano tiene una coloración de grafo de sus vértices con cuatro colores, pero Tait mostró cómo convertir coloraciones de 4 vértices de grafos planos maximalistas en coloraciones de 3 aristas de sus grafos duales , que son cúbicos y planos, y viceversa. Por lo tanto, un snark plano sería necesariamente dual con un contraejemplo del teorema de los cuatro colores. Por lo tanto, la prueba posterior del teorema de los cuatro colores [17] también demuestra que todos los snarks son no planos. [18]
Todos los snarks son no hamiltonianos : cuando un grafo cúbico tiene un ciclo hamiltoniano, siempre es posible colorear 3 veces sus aristas, utilizando dos colores en alternancia para el ciclo y el tercer color para las aristas restantes. Sin embargo, muchos snarks conocidos están cerca de ser hamiltonianos, en el sentido de que son grafos hipohamiltonianos : la eliminación de cualquier vértice deja un subgrafo hamiltoniano. Un snark hipohamiltoniano debe ser bicrítico : la eliminación de dos vértices cualesquiera deja un subgrafo de tres aristas coloreables. [19] La rareza de un grafo cúbico se define como el número mínimo de ciclos impares, en cualquier sistema de ciclos que cubre cada vértice una vez (un 2-factor ). Por la misma razón que no tienen ciclos hamiltonianos, los snarks tienen rareza positiva: un 2-factor completamente par conduciría a una coloración de 3 aristas, y viceversa. Es posible construir infinitas familias de snarks cuya rareza crece linealmente con su número de vértices. [14]
La conjetura de la doble cobertura de ciclos postula que en cada grafo sin puentes se puede encontrar una colección de ciclos que cubren cada arista dos veces, o equivalentemente que el grafo puede ser incrustado en una superficie de tal manera que todas las caras de la incrustación sean ciclos simples. Cuando un grafo cúbico tiene una coloración de 3 aristas, tiene una doble cobertura de ciclos que consiste en los ciclos formados por cada par de colores. Por lo tanto, entre los grafos cúbicos, los snarks son los únicos contraejemplos posibles. De manera más general, los snarks forman el caso difícil para esta conjetura: si es verdad para los snarks, es verdad para todos los grafos. [20] En relación con esto, Branko Grünbaum conjeturó que ningún snark podría ser incrustado en una superficie de tal manera que todas las caras sean ciclos simples y tal que cada dos caras sean disjuntas o compartan solo una arista; si cualquier snark tuviera tal incrustación, sus caras formarían una doble cobertura de ciclos. Sin embargo, Martin Kochol encontró un contraejemplo a la conjetura de Grünbaum. [21]
Determinar si un gráfico cúbico cíclico 5-conexo es coloreable en 3 aristas es NP-completo . Por lo tanto, determinar si un gráfico es un snark es co-NP-completo . [22]
WT Tutte conjeturó que cada snark tiene el grafo de Petersen como menor . Es decir, conjeturó que el snark más pequeño, el grafo de Petersen, puede formarse a partir de cualquier otro snark contrayendo algunas aristas y eliminando otras. De manera equivalente (porque el grafo de Petersen tiene un grado máximo de tres) cada snark tiene un subgrafo que puede formarse a partir del grafo de Petersen subdividiendo algunas de sus aristas . Esta conjetura es una forma reforzada del teorema de los cuatro colores , porque cualquier grafo que contenga el grafo de Petersen como menor debe ser no plano. En 1999, Neil Robertson , Daniel P. Sanders , Paul Seymour y Robin Thomas anunciaron una prueba de esta conjetura. [23] Se han publicado pasos hacia este resultado en 2016 y 2019, [24] [25] pero la prueba completa sigue sin publicarse. [18] Véase la conjetura de Hadwiger para otros problemas y resultados relacionados con la coloración de gráficos con los menores de gráficos.
Tutte también conjeturó una generalización a grafos arbitrarios: cada grafo sin puentes y sin menor de Petersen tiene un 4-flujo cero en ninguna parte . Es decir, a los bordes del grafo se les puede asignar una dirección y un número del conjunto {1, 2, 3}, de modo 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ó Tutte, para los grafos cúbicos tal asignación existe si y solo si los bordes pueden colorearse con tres colores, por lo que la conjetura se seguiría de la conjetura de snark en este caso. Sin embargo, probar la conjetura de snark no resolvería la cuestión de la existencia de 4-flujos para grafos no cúbicos. [26]
