En el campo matemático de la teoría de grafos , un snark es un gráfico no dirigido con exactamente tres aristas por vértice cuyas aristas no pueden colorearse con solo tres colores. Para evitar casos triviales, a los snarks a menudo se les imponen requisitos adicionales en cuanto a su conectividad y a la duración de sus ciclos . Existen infinitos sarcásticos.
Una de las formas equivalentes del teorema de los cuatro colores es que todo snark es un gráfico 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 de la teoría de grafos. : en el Electronic Journal of Combinatorics , Miroslav Chladný y Martin Škoviera afirman que
En el estudio de varios problemas importantes y difíciles de la teoría de grafos (como la conjetura de la doble cobertura del ciclo y la conjetura de los 5 flujos ), uno encuentra una variedad interesante pero algo misteriosa de grafos llamados snarks. A pesar de su sencilla definición... y de más de un siglo de investigación, sus propiedades y estructura son en gran medida desconocidas. [1]
Además de los problemas que mencionan, la conjetura snark de WT Tutte se refiere a la existencia de gráficos de Petersen como gráficos menores de snarks; su prueba se ha anunciado desde hace mucho tiempo, pero permanece inédita, y resolvería un caso especial de existencia de 4 flujos cero en ninguna parte .
Los Snarks fueron nombrados así por el matemático estadounidense Martin Gardner en 1976, en honor al misterioso y esquivo objeto del poema La caza del Snark de Lewis Carroll . [2] Sin embargo, el estudio de esta clase de gráficos 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 equivale a la afirmación de que ningún snark es plano . [3] El primer gráfico conocido por ser sarcástico fue el gráfico de Petersen ; Julius Petersen demostró que era un sarcástico 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 infinitas familias 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 flor: el snark de estrella doble . [9] El snark Watkins de 50 vértices fue descubierto en 1989. [10]
Otro gráfico cúbico notable que no se puede colorear con tres aristas es el gráfico de Tietze , con 12 vértices; como descubrió Heinrich Franz Friedrich Tietze en 1910, forma el límite de una subdivisión de la franja de Möbius que requiere seis colores. [11] Sin embargo, debido a que contiene un triángulo, generalmente no se considera un snark. Según definiciones estrictas de snarks, los snarks más pequeños son el gráfico 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 en 2012 una lista de todos los snarks hasta 36 vértices (según una definición estricta) y hasta 34 vértices (según una definición más débil) . ] 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 según el lema del protocolo de enlace .) [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 gráficos cúbicos (que tienen exactamente tres aristas en cada vértice) cuyos bordes no se pueden colorear con solo tres colores. Según el teorema de Vizing , el número de colores necesarios para los bordes de un gráfico cúbico es tres (gráficos de "clase uno") o cuatro (gráficos de "clase dos"), por lo que los snarks son gráficos cúbicos de clase dos. Sin embargo, para evitar casos en los que un snark sea de clase dos por razones triviales, o se construya de forma trivial a partir de gráficos más pequeños, a menudo se imponen restricciones adicionales en la conectividad y la duración de los ciclos. En particular:
Aunque estas definiciones sólo consideran restricciones de circunferencia de hasta cinco, existen snarks con circunferencia arbitrariamente grande. [dieciséis]
El trabajo de Peter G. Tait estableció que el teorema de los cuatro colores es verdadero si y sólo si todo snark no es plano. [3] Este teorema establece que cada gráfico plano tiene una coloración gráfica de sus vértices con cuatro colores, pero Tait mostró cómo convertir coloraciones de 4 vértices de gráficos planos máximos en coloraciones de 3 bordes de sus gráficos duales , que son cúbica y plana, y viceversa. Por lo tanto, un snark plano sería necesariamente dual con respecto a un contraejemplo del teorema de los cuatro colores. Así, la prueba posterior del teorema de los cuatro colores [17] también demuestra que todos los snarks no son planos. [18]
Todos los snarks son no hamiltonianos : cuando un gráfico cúbico tiene un ciclo hamiltoniano, siempre es posible colorear sus aristas con 3 colores, utilizando dos colores alternativamente 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 gráficos 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 coloreable de tres bordes. [19] La imparidad de un gráfico cúbico se define como el número mínimo de ciclos impares, en cualquier sistema de ciclos que cubra cada vértice una vez (un factor de 2 ). Por la misma razón que no tienen ciclos hamiltonianos, los snarks tienen una rareza positiva: un factor 2 completamente par conduciría a una coloración de 3 bordes, 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 del ciclo postula que en cada gráfico sin puente se puede encontrar una colección 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 de la incrustación sean ciclos simples. Cuando un gráfico cúbico tiene una coloración de 3 aristas, tiene una doble cobertura de ciclo que consta de los ciclos formados por cada par de colores. Por tanto, entre los grafos cúbicos, los snarks son los únicos contraejemplos posibles. De manera más general, los snarks constituyen el caso difícil para esta conjetura: si es cierta para los snarks, también lo es para todos los grafos. [20] En este sentido, Branko Grünbaum conjeturó que ningún snark podría incrustarse en una superficie de tal manera que todas las caras sean ciclos simples y que cada dos caras sean disjuntas o compartan solo un borde; si algún snark tuviera tal incrustación, sus caras formarían una doble cubierta cíclica. Sin embargo, Martin Kochol encontró un contraejemplo a la conjetura de Grünbaum. [21]
Determinar si un gráfico cúbico dado de 5 conexiones cíclicas 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 todo snark tiene el gráfico de Petersen como menor . Es decir, conjeturó que el snark más pequeño, el gráfico de Petersen, puede formarse a partir de cualquier otro snark contrayendo algunos bordes y eliminando otros. De manera equivalente (debido a que el gráfico de Petersen tiene un grado máximo de tres), cada snark tiene un subgrafo que se puede formar a partir del gráfico de Petersen subdividiendo algunos de sus bordes . Esta conjetura es una forma reforzada del teorema de los cuatro colores , porque cualquier gráfico que contenga el gráfico 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] Los pasos hacia este resultado se publicaron en 2016 y 2019, [24] [25] pero la prueba completa permanece inédita. [18] Consulte la conjetura de Hadwiger para conocer otros problemas y resultados relacionados con la coloración de gráficos con gráficos menores.
Tutte también conjeturó una generalización a gráficos arbitrarios: cada gráfico sin puente sin menor de Petersen tiene un flujo 4 en ninguna parte cero . Es decir, a los bordes del gráfico 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 gráficos cúbicos tal asignación existe si y solo si los bordes pueden colorearse con tres colores, por lo que la conjetura se derivaría de la conjetura de Snark en este caso. Sin embargo, demostrar la conjetura de Snark no resolvería la cuestión de la existencia de 4 flujos para gráficos no cúbicos. [26]
