En teoría de grafos , el teorema de Vizing establece que todo grafo simple no dirigido puede colorearse con un número de colores que sea como máximo uno mayor que el grado máximo Δ del grafo. Siempre son necesarios al menos Δ colores, por lo que los grafos no dirigidos pueden dividirse en dos clases: grafos de "clase uno" para los que son suficientes Δ colores, y grafos de "clase dos" para los que son necesarios Δ + 1 colores. Una versión más general del teorema de Vizing establece que todo multigrafo no dirigido sin bucles puede colorearse con como máximo Δ+µ colores, donde µ es la multiplicidad del multigrafo. [1] El teorema recibe su nombre de Vadim G. Vizing, quien lo publicó en 1964.
El teorema descubierto por el matemático soviético Vadim G. Vizing fue publicado en 1964 cuando Vizing trabajaba en Novosibirsk y se lo conoció como el teorema de Vizing. [2] El matemático indio RP Gupta descubrió el teorema de forma independiente mientras realizaba su doctorado (1965-1967). [3] [4]
Cuando Δ = 1 , el grafo G debe ser en sí mismo un grafo coincidente, sin dos aristas adyacentes, y su número cromático de aristas es uno. Es decir, todos los grafos con Δ( G ) = 1 son de clase uno.
Cuando Δ = 2 , el grafo G debe ser una unión disjunta de caminos y ciclos . Si todos los ciclos son pares, se pueden colorear en dos aristas alternando los dos colores alrededor de cada ciclo. Sin embargo, si existe al menos un ciclo impar, entonces no es posible colorear en dos aristas. Es decir, un grafo con Δ = 2 es de clase uno si y solo si es bipartito .
Esta prueba está inspirada en Diestel (2000).
Sea G = ( V , E ) un grafo simple no dirigido. Procedemos por inducción sobre m , el número de aristas. Si el grafo está vacío, el teorema se cumple trivialmente. Sea m > 0 y supongamos que existe una coloración de aristas (Δ+1) adecuada para todo G − xy donde xy ∈ E .
Decimos que el color α ∈ {1,...,Δ+1 } falta en x ∈ V con respecto a la coloración de aristas (Δ+1) adecuada c si c ( xy ) ≠ α para todo y ∈ N( x ) . Además, sea α/β -path desde x la única ruta máxima que comienza en x con una arista de color α y alterna los colores de las aristas (la segunda arista tiene color β , la tercera arista tiene color α y así sucesivamente), su longitud puede ser 0 . Nótese que si c es una coloración de aristas (Δ+1) adecuada de G entonces cada vértice tiene un color faltante con respecto a c .
Supongamos que no existe una coloración de aristas (Δ+1) adecuada de G. Esto es equivalente a esta afirmación:
Esto es equivalente, porque si (1) no se cumple, entonces podemos intercambiar los colores α y β en la ruta α/β y establecer el color de xy como α , creando así una coloración de arista (Δ+1) adecuada de G a partir de c . A la inversa, si existe una coloración de arista (Δ+1) adecuada , entonces podemos eliminar xy , restringir la coloración y (1) tampoco se cumplirá.
Ahora, sea xy 0 ∈ E y c 0 una coloración de aristas (Δ+1) propia de G − xy 0 y α esté ausente en x con respecto a c 0. Definimos y 0 ,..., y k como una secuencia máxima de vecinos de x tal que c 0 ( xy i ) esté ausente en y i −1 con respecto a c 0 para todo 0 < i ≤ k .
Definimos las coloraciones c 1 ,..., c k como
Entonces c i es una coloración de arista (Δ+1) propia de G − xy i debido a la definición de y 0 ,..., y k . Además, note que los colores faltantes en x son los mismos con respecto a c i para todos los 0 ≤ i ≤ k .
Sea β el color que falta en y k con respecto a c 0 , entonces β también falta en y k con respecto a c i para todo 0 ≤ i ≤ k . Nótese que β no puede faltar en x , de lo contrario podríamos extender fácilmente c k , por lo tanto, una arista con color β es incidente en x para todo c j . De la maximalidad de k , existe 1 ≤ i < k tal que c 0 ( xy i ) = β . De la definición de c 1 ,..., c k se cumple:
Sea P el camino α/β desde y k con respecto a c k . De (1), P tiene que terminar en x . Pero α falta en x , por lo que tiene que terminar con una arista de color β . Por lo tanto, la última arista de P es y i −1 x . Ahora, sea P' el camino α/β desde y i −1 con respecto a c i −1 . Como P' está determinado de forma única y las aristas internas de P no se modifican en c 0 ,..., c k , el camino P' usa las mismas aristas que P en orden inverso y visita y k . La arista que conduce a y k claramente tiene color α . Pero β falta en y k , por lo que P' termina en y k . Lo cual es una contradicción con (1) anterior.
Varios autores han proporcionado condiciones adicionales que clasifican algunos grafos como de clase uno o clase dos, pero no proporcionan una clasificación completa. Por ejemplo, si los vértices del grado máximo Δ en un grafo G forman un conjunto independiente , o más generalmente si el subgrafo inducido para este conjunto de vértices es un bosque, entonces G debe ser de clase uno. [5]
Erdős y Wilson (1977) demostraron que casi todos los grafos son de clase uno. Es decir, en el modelo de Erdős–Rényi de grafos aleatorios, en el que todos los grafos de n vértices tienen la misma probabilidad, sea p ( n ) la probabilidad de que un grafo de n vértices extraído de esta distribución sea de clase uno; entonces p ( n ) se aproxima a uno en el límite cuando n tiende a infinito. Para límites más precisos sobre la tasa a la que p ( n ) converge a uno, véase Frieze et al. (1988).
Vizing (1965) demostró que un grafo plano es de clase uno si su grado máximo es al menos ocho. En cambio, observó que para cualquier grado máximo en el rango de dos a cinco, existen grafos planos de clase dos. Para el grado dos, cualquier ciclo impar es un grafo de este tipo, y para los grados tres, cuatro y cinco, estos grafos pueden construirse a partir de sólidos platónicos reemplazando una única arista por un camino de dos aristas adyacentes.
En la conjetura de grafos planares de Vizing , Vizing (1965) afirma que todos los grafos planares simples con grado máximo seis o siete son de clase uno, cerrando los casos posibles restantes. Independientemente, Zhang (2000) y Sanders & Zhao (2001) demostraron parcialmente la conjetura de grafos planares de Vizing al mostrar que todos los grafos planares con grado máximo siete son de clase uno. Por lo tanto, el único caso de la conjetura que permanece sin resolver es el de grado máximo seis. Esta conjetura tiene implicaciones para la conjetura de coloración total .
Los grafos planares de clase dos construidos por subdivisión de los sólidos platónicos no son regulares: tienen vértices de grado dos así como vértices de grado superior. El teorema de los cuatro colores (demostrado por Appel y Haken (1976)) sobre la coloración de los vértices de los grafos planares, es equivalente a la afirmación de que todo grafo planar 3-regular sin puentes es de clase uno (Tait 1880).
En 1969, Branko Grünbaum conjeturó que todo grafo 3-regular con una incrustación poliédrica en cualquier variedad orientada bidimensional, como un toro, debe ser de clase uno. En este contexto, una incrustación poliédrica es una incrustación de grafo tal que cada cara de la incrustación es topológicamente un disco y tal que el grafo dual de la incrustación es simple, sin bucles propios ni adyacencias múltiples. Si fuera cierto, esto sería una generalización del teorema de los cuatro colores, que Tait demostró que es equivalente a la afirmación de que los grafos 3-regulares con una incrustación poliédrica en una esfera son de clase uno. Sin embargo, Kochol (2009) demostró que la conjetura era falsa al encontrar snarks que tienen incrustaciones poliédricas en superficies orientables de género alto. Basándose en esta construcción, también demostró que es NP-completo determinar si un gráfico poliédricamente incrustado es de clase uno. [6]
Misra y Gries (1992) describen un algoritmo de tiempo polinomial para colorear los bordes de cualquier gráfico con Δ + 1 colores, donde Δ es el grado máximo del gráfico. Es decir, el algoritmo utiliza el número óptimo de colores para gráficos de clase dos y utiliza como máximo un color más de lo necesario para todos los gráficos. Su algoritmo sigue la misma estrategia que la prueba original del teorema de Vizing: comienza con un gráfico sin colorear y luego encuentra repetidamente una forma de volver a colorear el gráfico para aumentar en uno el número de bordes coloreados.
Más específicamente, supongamos que uv es una arista sin color en un grafo parcialmente coloreado. El algoritmo de Misra y Gries puede interpretarse como la construcción de un pseudobosque dirigido P (un grafo en el que cada vértice tiene como máximo una arista saliente) sobre los vecinos de u : para cada vecino p de u , el algoritmo encuentra un color c que no es utilizado por ninguna de las aristas incidentes a p , encuentra el vértice q (si existe) para el cual la arista uq tiene color c , y agrega pq como arista a P . Hay dos casos:
Con algunas estructuras de datos simples para llevar un registro de los colores que se usan y están disponibles en cada vértice, la construcción de P y los pasos de recoloración del algoritmo se pueden implementar en un tiempo O( n ) , donde n es el número de vértices en el gráfico de entrada. Dado que estos pasos deben repetirse m veces, y cada repetición aumenta el número de aristas coloreadas en uno, el tiempo total es O( mn ) .
En un informe técnico no publicado, Gabow et al. (1985) afirmaron un límite de tiempo más rápido para el mismo problema de coloración con Δ + 1 colores.
En Gutin & Toft (2000) y Soifer (2008), Vizing menciona que su trabajo estuvo motivado por un teorema de Shannon (1949) que mostraba que los multigrafos podían colorearse con (3/2)Δ colores como máximo. Aunque el teorema de Vizing es ahora material estándar en muchos libros de texto de teoría de grafos, Vizing tuvo problemas inicialmente para publicar el resultado, y su artículo al respecto aparece en una revista poco conocida, Diskret. Analiz . [7]
