Ver el código de «Snark (teoría de grafos)»

{{Main|Teoría de grafos}}
[[Archivo:Petersen1 tiny.svg|miniaturadeimagen|El [[grafo de Petersen]] es el snark más pequeño.]]
En el campo [[Matemáticas|matemático]] de la [[teoría de grafos]], un '''''snark''''' es un grafo no dirigido con exactamente tres aristas por [[Vértice (teoría de grafos)|vértice]] cuyas aristas no pueden colorearse con sólo tres colores. Para evitar casos triviales, los snarks suelen tener requisitos adicionales en cuanto a su conectividad y a la [[Grafo de cinta|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 [[Grafo plano|plano]]. La investigación sobre los snarks tiene su origen en los trabajos de [[Peter G. Tait]] sobre el teorema de los cuatro colores en 1880, pero su nombre es mucho más reciente, ya que se lo dio [[Martin Gardner]] en 1976. Más allá de la coloración, los snarks también están relacionados con otros problemas difíciles de la teoría de grafos: en el ''Electronic Journal of Combinatorics'', Miroslav Chladný y Martin Škoviera afirman que:<blockquote>En el estudio de varios problemas importantes y difíciles de la teoría de grafos (como la conjetura del [[ciclo doble tapa]] y la conjetura de los [[5 flujos en flujo cero en ninguna parte]] (''nowhere-zero flow)'', uno se encuentra con una interesante pero algo misteriosa variedad 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 parte desconocidas.<ref>{{Cita publicación|título="Factorisation of snarks"|apellidos=Chladný, Miroslav; Škoviera, Martin|fecha=2010|publicación=Electronic Journal of Combinatorics|doi=10.37236/304}}</ref></blockquote>
[[Archivo:Flower snarkv.svg|miniaturadeimagen|El snark flor J<sub>5</sub> es una de las seis snarks en 20 [[Vértice (teoría de grafos)|vértices]].]]
Además de los problemas que mencionan, la conjetura snark de [[W. T. Tutte]] se refiere a la existencia de [[Grafo de Petersen|grafos de Petersen]] como grafos menores de snarks; su demostración se ha anunciado hace tiempo pero sigue sin publicarse, y resolvería un caso especial de la existencia de [[4-flujos en flujo cero en ninguna parte]].

== Historia y ejemplos ==
Los snarks fueron bautizados así por el matemático estadounidense [[Martin Gardner]] en 1976, en honor al misterioso y escurridizo objeto del poema ''[[La caza del Snark]]'' de [[Lewis Carroll]].<ref name=":0">{{Cita publicación|título="Snarks, boojums, and other conjectures related to the four-color-map theorem"|apellidos=Gardner, Martin|fecha=1976|publicación=Mathematical Games, Scientific American|doi=10.1038/scientificamerican0476-126}}</ref> Sin embargo, el estudio de esta clase de grafos es bastante 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 [[Grafo plano|plano]].<ref name=":1">{{Cita publicación|título="Remarks on the colourings of maps"|apellidos=Tait, Peter Guthrie|fecha=1880|publicación=Proceedings of the Royal Society of Edinburgh|doi=10.1017/S0370164600044643}}</ref> El primer gráfico conocido como snark fue el gráfico de Petersen; [[Julius Petersen]] demostró que era un snark en 1898,<ref>{{Cita libro|título=L'Intermédiaire des mathematiciens|url=https://archive.org/details/lintermdiairede03lemogoog/page/n239|editorial=Paris : Gauthier-Villars et Fils|fecha=1894|fechaacceso=2024-09-23|apellidos=University of Michigan|nombre=Emile Michel Hyacinthe Lemoine}}</ref> aunque [[Alfred Kempe]] ya lo había estudiado con un propósito diferente en 1886.<ref>{{Cita publicación|título="A memoir on the theory of mathematical form"|apellidos=Kempe, A. B.|fecha=1886|publicación=Philosophical Transactions of the Royal Society of London|doi=10.1098/rstl.1886.0002}}</ref>

Los siguientes cuatro snarks conocidos fueron:

* los ''snarks de Blanuša'' (dos con 18 [[Vértice (teoría de grafos)|vértices]]), descubiertos por [[Danilo Blanuša]] en 1946,<ref>{{Cita publicación|título="Le problème des quatre couleurs"|apellidos=Blanuša, Danilo|fecha=1946|publicación=Glasnik Matematičko-Fizički i Astronomski,}}</ref>
* el ''snark Descartes'' (210 vértices), descubierto por [[Bill Tuttle|Bill Tutte]] en 1948, y<ref>{{Cita publicación|título=Network-colourings|apellidos=Descartes, Blanche|fecha=1948|publicación=The Mathematical Gazette|doi=10.2307/3610702}}</ref>
* el ''snark Szekeres'' (50 vértices), descubierto por [[George Szekeres]] en 1973.<ref>{{Cita publicación|título="Polyhedral decompositions of cubic graphs"|apellidos=Szekeres, George|fecha=1973|publicación=Bulletin of the Australian Mathematical Society|doi=10.1017/S0004972700042660}}</ref>

En 1975, Rufus Isaacs generalizó el método de Blanuša para construir dos familias infinitas de snarks: los ''[[snarks flor]]'' y los ''[[snarks Blanuša-Descartes-Szekeres]]'', una familia que incluye los dos snarks de Blanuša, el snark Descartes y el snark 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 doble estrella''.<ref name=":2">{{Cita publicación|título="Infinite families of non-trivial trivalent graphs which are not Tait-colorable"|apellidos=Isaacs, Rufus|fecha=1975|publicación=The American Mathematical Monthly|doi=10.2307/2319844}}</ref> En 1989 se descubrió el ''snark de 50 vértices'' de [[Snark de Watkins|Watkins]].<ref>{{Cita publicación|título="Snarks"|apellidos=Watkins, John J.|fecha=1989|publicación=Graph theory and its Applications: East and West, Proceedings of the First China–USA International Conference held in Jinan, June 9–20, 1986, Annals of the New York Academy of Sciences, vol. 576, New York: New York Academy of Sciences|doi=10.1111/j.1749-6632.1989.tb16441.x}}</ref>

Otro notable [[grafo cúbico]] no coloreable 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.<ref>{{Cita publicación|url=https://sites.math.washington.edu/~mathcircle/circle/2014-15/advanced/mc-14a-w8.pdf|título="Einige Bemerkungen zum Problem des Kartenfärbens auf einseitigen Flächen"|apellidos=Tietze, Heinrich|fecha=1910|publicación=DMV Annual Report}}</ref> Sin embargo, debido a que contiene un triángulo, generalmente no se 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.<ref name=":3">{{Cita publicación|título=Generation and properties of snarks"|apellidos=Brinkmann, Gunnar; Goedgebeur, Jan; Hägglund, Jonas; Markström, Klas|fecha=2012|publicación=Journal of Combinatorial Theory, Series B|doi=10.1016/j.jctb.2013.05.001}}</ref>

[[Gunnar Brinkmann]], [[Jan Goedgebeur]], [[Jonas Hägglund]] y [[Klas Markström]] generaron en 2012 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).<ref name=":3" /> El número de snarks para un número par de vértices dado crece al menos exponencialmente en el número de vértices.<ref>{{Cita publicación|título=Exponentially many hypohamiltonian snarks|apellidos=Skupień, Zdzisław|fecha=2007|publicación=6th Czech-Slovak International Symposium on Combinatorics, Graph Theory, Algorithms and Applications, Electronic Notes in Discrete Mathematics|doi=10.1016/j.endm.2007.01.059}}</ref> Dado que tienen vértices de grado impar, todos los snarks deben tener un número par de vértices por el [[lema del apretón de manos]]).<ref name=":4">{{Cita publicación|título=Small snarks with large oddness|apellidos=Lukot'ka, Robert; Máčajová, Edita; Mazák, Ján; Škoviera, Martin|fecha=2015|publicación=Electronic Journal of Combinatorics|doi=10.37236/3969}}</ref> La secuencia A130315 de la [[OEIS]] contiene el número de snarks no triviales de <math>2n</math> vértices para valores pequeños de <math>n</math>. <ref>{{Cita web|url=https://oeis.org/A130315|título=A130315 - OEIS|fechaacceso=2024-09-23|sitioweb=oeis.org}}</ref>

== Definición ==
La definición precisa de snarks varía según los autores,<ref name=":2" /><ref name=":3" /> pero generalmente se refiere a [[Grafo cúbico|grafos cúbicos]] (que tienen exactamente tres [[aristas]] en cada vértice) cuyas aristas no pueden colorearse con sólo tres colores. Según el [[teorema de Vizing]], el número de colores necesarios para las aristas de un grafo cúbico es tres (grafos de «clase uno») o cuatro (grafos de «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 forma trivial a partir de grafos más pequeños, a menudo se imponen restricciones adicionales sobre la conectividad y la longitud de los ciclos. En particular:

* Si un grafo cúbico tiene un [[Puente (teoria de grafos)|puente]], una arista cuya eliminación lo desconectaría, entonces no puede ser de clase uno. Por el [[lema del apretón de manos]], los subgrafos a ambos lados del puente tienen un número impar de vértices cada uno. Cualquiera que sea el color elegido para el puente, su número impar de vértices impide que estos [[Subgrafo|subgrafos]] estén cubiertos por ciclos que alternan entre los otros dos colores, como sería necesario en una coloración de 3 aristas. Por esta razón, generalmente se requiere que los snarks no tengan puentes.<ref name=":0" /><ref name=":2" />
* Un [[Bucle (teoría de grafos)|bucle]] (una arista que conecta un vértice consigo misma) no puede colorearse sin que el mismo color aparezca dos veces en ese vértice, lo que supone una violación de los requisitos habituales para la coloración de aristas de grafos. Además, un ciclo formado por dos vértices conectados por dos aristas siempre puede sustituirse por una única arista que conecte a sus otros dos vecinos, lo que simplifica el grafo sin cambiar su coloreabilidad de tres aristas. Por estas razones, los snarks se limitan generalmente a [[Grafo|grafos simples]], sin bucles ni adyacencias múltiples.<ref name=":2" />
* Si un grafo contiene un triángulo, puede simplificarse de nuevo sin cambiar su coloreabilidad en tres aristas, contrayendo los tres vértices del triángulo en un único vértice. Por lo tanto, muchas definiciones de snarks prohíben los triángulos.<ref name=":2" /> Sin embargo, aunque este requisito también se estableció en el trabajo de Gardner que dio el nombre de «snark» a estos grafos, Gardner incluye el [[grafo de Tietze]], que contiene un triángulo, como un snark.<ref name=":0" />
* Si un grafo contiene un ciclo de cuatro vértices, puede simplificarse de dos maneras diferentes eliminando dos aristas opuestas del ciclo y sustituyendo los caminos resultantes de vértices de grado dos por aristas simples. Tiene una coloración de tres aristas si y sólo si al menos una de estas simplificaciones la tiene. Por lo tanto, Isaacs requiere que un grafo cúbico «no trivial» de clase dos evite ciclos de cuatro vértices,<ref name=":2" /> y otros autores han seguido su ejemplo prohibiendo estos ciclos.<ref name=":3" /> El requisito de que un snark evite ciclos de longitud cuatro o menos puede resumirse afirmando que la [[Grafo de cinta|circunferencia]] de estos grafos, la longitud de sus ciclos más cortos, es al menos cinco.
* En concreto, la definición utilizada por Brinkmann et al. (2012) exige que los snarks estén conectados cíclicamente por 4 aristas. Esto significa que no puede haber ningún [[subconjunto]] de tres o menos aristas cuya eliminación desconectaría el grafo en dos [[Subgrafo|subgrafos]], cada uno de los cuales tiene al menos un ciclo. Brinkmann et al. definen un snark como un grafo cúbico y cíclicamente conectado por 4 aristas de circunferencia cinco o más y clase dos; definen un «snark débil» para permitir circunferencia cuatro.<ref name=":3" />

Aunque estas definiciones sólo consideran restricciones en la circunferencia hasta cinco, existen snarks con circunferencias arbitrariamente grandes.<ref>{{Cita publicación|título="Snarks without small cycles"|apellidos=Kochol, Martin|fecha=1996|publicación=Journal of Combinatorial Theory, Series B|doi=10.1006/jctb.1996.0032}}</ref>

== Propiedades ==
El trabajo de [[Peter G. Tait]] estableció que el [[teorema de los cuatro colores]] es cierto si y sólo si cada snark no es planar.<ref name=":1" /> Este teorema establece que cada [[Grafo plano|grafo planar]] tiene una coloración de sus vértices con cuatro colores, pero Tait demostró cómo convertir coloraciones de 4 vértices de grafos planares máximos en coloraciones de 3 aristas de sus [[Grafo dual|grafos duales]], que son cúbicos y planares, y viceversa. Por tanto, un snark plano sería necesariamente dual a un contraejemplo del teorema de los cuatro colores.<ref>{{Cita publicación|url=https://projecteuclid.org/journals/bulletin-of-the-american-mathematical-society-new-series/volume-82/issue-5/Every-planar-map-is-four-colorable/bams/1183538218.full|título=Every planar map is four colorable|apellidos=Appel|nombre=K.|apellidos2=Haken|nombre2=W.|fecha=1976-09|publicación=Bulletin of the American Mathematical Society|volumen=82|número=5|páginas=711–712|fechaacceso=2024-09-23|issn=0002-9904}}</ref> Así, la prueba posterior del teorema de los cuatro colores también demuestra que todos los snarks no son planares.<ref name=":5">{{Cita publicación|título=The continuing saga of snarks|apellidos=belcastro, sarah-marie|fecha=2012|publicación=The College Mathematics Journal|doi=10.4169/college.math.j.43.1.082}}</ref>

Todos los snarks son no [[Camino hamiltoniano|hamiltonianos]]: cuando un grafo cúbico tiene un ciclo hamiltoniano, siempre es posible colorear sus aristas en 3 colores, 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 [[Grafo hipohamiltoniano|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.<ref>{{Cita publicación|título=Classification and characterizations of snarks"|apellidos=Steffen, E.|fecha=1998|publicación=Discrete Mathematics|doi=10.1016/S0012-365X(97)00255-0}}</ref> La [[Impar|imparidad]] de un grafo 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 2). 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. Es posible construir infinitas familias de snarks cuya imparidad crece linealmente con su número de vértices.<ref name=":4" />

La [[Ciclo de doble tapa|conjetura de la doble cubierta de ciclos]] postula que en todo grafo sin puentes se puede encontrar una colección de ciclos que cubren dos veces cada arista, o lo que es lo mismo, que el grafo se puede incrustar en una superficie de forma 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 formada por los ciclos formados por cada par de colores. Por lo tanto, entre los grafos cúbicos, los snarks son los únicos contraejemplos posibles. De forma más general, los snarks constituyen el caso difícil de esta conjetura: si es cierta para los snarks, lo es para todos los grafos.<ref>{{Cita publicación|título=A survey of the cycle double cover conjecture|apellidos=Jaeger, François|fecha=1985|publicación=Alspach, B. R.; Godsil, C. D. (eds.), Annals of Discrete Mathematics 27: Cycles in Graphs, North-Holland Mathematics Studies|doi=10.1016/S0304-0208(08)72993-1}}</ref> 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.<ref>{{Cita publicación|título=Polyhedral embeddings of snarks in orientable surfaces|apellidos=Kochol, Martin|fecha=2009|publicación=Proceedings of the American Mathematical Society}}</ref>

Determinar si un grafo cúbico de 5 conexiones cíclicas es coloreable por 3 aristas es [[NP-completo]]. Por lo tanto, determinar si un grafo es un snark es [[co-NP-completo]].<ref>{{Cita publicación|título=Complexity of 3-edge-coloring in the class of cubic graphs with a polyhedral embedding in an orientable surface|apellidos=Kochol, Martin|fecha=2010|publicación=Discrete Applied Mathematics|doi=10.1016/j.dam.2010.06.019}}</ref>

== Conjetura Snark ==
[[W. T. Tutte]] conjeturó que cada snark tiene el [[grafo de Petersen]] como [[Menor (teoría de grafos)|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 forma equivalente (ya que 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 [[Homeomorfismo|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.<ref>{{Cita publicación|url=https://people.math.gatech.edu/~thomas/PAP/bcc.pdf|título="Recent excluded minor theorems for graphs"|apellidos=Thomas, Robin|fecha=1999|publicación=Surveys in Combinatorics. Cambridge University Press}}</ref> Pasos hacia este resultado se han publicado en 2016 y 2019,<ref>{{Cita publicación|url=https://web.math.princeton.edu/~pds/papers/cubxx/paper.pdf|título="Three-edge-colouring doublecross cubic graphs"|apellidos=Edwards, Katherine; Sanders, Daniel P.; Seymour, Paul; Thomas, Robin|fecha=2016|publicación=Journal of Combinatorial Theory, Series B|doi=10.1016/j.jctb.2015.12.006}}</ref><ref>{{Cita publicación|título=Excluded minors in cubic graphs|apellidos=Robertson, Neil; Seymour, Paul; Thomas, Robin|fecha=2019|publicación=Journal of Combinatorial Theory, Series B|doi=10.1016/j.jctb.2019.02.002}}</ref> pero la prueba completa sigue sin publicarse.<ref name=":5" /> Véase la [[conjetura de Hadwiger]] para otros problemas y resultados relacionados con la coloración de grafos y grafos menores.

Tutte también conjeturó una generalización para grafos arbitrarios: todo grafo sin puentes y sin Petersen menor tiene un 4-flujos en cero en ninguna parte . Es decir, a las [[aristas]] del grafo se les puede asignar una dirección y un número del conjunto {1, 2, 3}, tal 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 demostró Tutte, para [[Grafo cúbico|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. Sin embargo, demostrar la conjetura snark no resolvería la cuestión de la existencia de flujos de 4 para grafos no cúbicos.<ref>{{Cita publicación|url=https://garden.irmacs.sfu.ca/?q=op/4_flow_conjecture|título="4-flow conjecture"|apellidos=DeVos, Matthew|fecha=2007|publicación=Open Problem Garden}}</ref>

==Referencias==
{{Reflist}}

== Enlaces externos ==

* Weisstein, Eric W., «[https://mathworld.wolfram.com/Snark.html Snark]», MathWorld
{{Control de autoridades}}
[[Categoría:Grafos]]
[[Categoría:Grafos planares]]
[[Categoría:Grafos regulares]]
[[Categoría:Teoría de grafos]]