Ciclo doble cubierta
En matemáticas de teoría de grafos , una cubierta doble de ciclo es una colección de ciclos en un gráfico no dirigido que juntos incluyen cada borde del gráfico exactamente dos veces. Por ejemplo, para cualquier gráfico poliédrico , las caras de un poliedro convexo que representa el gráfico proporcionan una doble cobertura del gráfico: cada borde pertenece exactamente a dos caras.
Es un problema sin resolver, planteado por George Szekeres [1] y Paul Seymour [2] y conocido como la conjetura de la doble cubierta del ciclo , si cada gráfico sin puente tiene una cubierta doble del ciclo. La conjetura se puede formular de manera equivalente en términos de incrustaciones de gráficos , y en ese contexto también se conoce como la conjetura de incrustación circular .
La formulación habitual de la conjetura de la doble cubierta del ciclo pregunta si cada gráfico no dirigido sin puente tiene una colección de ciclos tal que cada borde del gráfico esté contenido exactamente en dos de los ciclos. El requisito de que el grafo no tenga puentes es una condición necesaria obvia para que exista tal conjunto de ciclos, porque un puente no puede pertenecer a ningún ciclo. Una colección de ciclos que satisfacen la condición de la conjetura de doble cobertura de ciclo se denomina doble cobertura de ciclo . Algunos gráficos, como los gráficos de ciclo y los gráficos de cactus sin puente , solo se pueden cubrir usando el mismo ciclo más de una vez, por lo que este tipo de duplicación se permite en una cubierta doble de ciclo.
Un snark es un caso especial de un gráfico sin puente, que tiene las propiedades adicionales de que cada vértice tiene exactamente tres aristas incidentes (es decir, el gráfico es cúbico ) y que no es posible dividir las aristas del gráfico en tres coincidencias perfectas ( es decir, el gráfico no tiene coloración de 3 aristas y, según el teorema de Vizing, tiene índice cromático 4). Resulta que los snarks forman el único caso difícil de la conjetura de la doble cubierta del ciclo: si la conjetura es cierta para los snarks, es cierta para cualquier gráfico. [3]
Jaeger (1985) observa que, en cualquier posible contraejemplo mínimo de la conjetura de la doble cubierta del ciclo, todos los vértices deben tener tres o más aristas incidentes. Porque un vértice con una sola arista incidente forma un puente, mientras que si dos aristas inciden en un vértice, uno puede contraerlas para formar un grafo más pequeño de modo que cualquier doble cubierta del grafo más pequeño se extienda a una del grafo original. Por otro lado, si un vértice vtiene cuatro o más aristas incidentes, uno puede "separar" dos de esas aristas retirándolas del gráfico y reemplazándolas por una única arista que conecta sus otros dos puntos finales, mientras se preserva la falta de puente del gráfico resultante. Una vez más, una doble cubierta del gráfico resultante puede extenderse de forma sencilla a una doble cubierta del gráfico original: cada ciclo del gráfico separado corresponde a un ciclo del gráfico original o a un par de ciclos que se encuentran en v. Así, todo contraejemplo mínimo debe ser cúbico. Pero si un gráfico cúbico puede tener sus aristas de 3 colores (por ejemplo, con los colores rojo, azul y verde), entonces el subgrafo de aristas rojas y azules, el subgrafo de aristas azules y verdes, y el subgrafo de aristas rojas y verdes cada uno forma una colección de ciclos separados que juntos cubren todos los bordes del gráfico dos veces. Por lo tanto, cada contraejemplo mínimo debe ser un gráfico cúbico sin puente coloreable que no tenga 3 aristas, es decir, un snark. [3]
