En teoría de grafos , el teorema de Vizing establece que cada gráfico simple no dirigido puede colorearse en los bordes utilizando un número de colores que sea como máximo uno mayor que el grado máximo Δ del gráfico. Al menos Δ colores siempre son necesarios, por lo que los gráficos no dirigidos se pueden dividir en dos clases: gráficos de "clase uno" para los cuales Δ colores son suficientes y gráficos de "clase dos" para los cuales Δ + 1 colores son necesarios. Una versión más general del teorema de Vizing establece que cada multigrafo no dirigido sin bucles puede colorearse como máximo con colores Δ+μ , donde µ es la multiplicidad del multigrafo. [1] El teorema lleva el nombre de Vadim G. Vizing , quien lo publicó en 1964.
El teorema descubierto por el matemático ruso Vadim G. Vizing se publicó en 1964 cuando Vizing trabajaba en Novosibirsk y pasó a ser conocido como el teorema de Vizing. [2] El matemático indio RP Gupta descubrió de forma independiente el teorema mientras realizaba su doctorado (1965-1967). [3] [4]
Cuando Δ = 1 , el gráfico G debe ser en sí mismo una coincidencia, sin dos aristas adyacentes, y su número cromático de arista es uno. Es decir, todas las gráficas con Δ( G ) = 1 son de clase uno.
Cuando Δ = 2 , el gráfico G debe ser una unión disjunta de caminos y ciclos . Si todos los ciclos son pares, se les puede colorear con 2 bordes alternando los dos colores alrededor de cada ciclo. Sin embargo, si existe al menos un ciclo impar, entonces no es posible colorear los 2 bordes. Es decir, una gráfica con Δ = 2 es de clase uno si y sólo si es bipartita .
Esta prueba está inspirada en Diestel (2000).
Sea G = ( V , E ) un gráfico simple no dirigido. Procedemos por inducción sobre m , el número de aristas. Si la gráfica está vacía, el teorema se cumple trivialmente. Sea m > 0 y supongamos que existe una coloración de borde (Δ+1) adecuada para todo G − xy donde xy ∈ E .
Decimos que falta el color α ∈ {1,...,Δ+1 } en x ∈ V con respecto a la coloración de bordes propia (Δ+1) c si c ( xy ) ≠ α para todo y ∈ N( X ) . Además, sea α/β -path desde x el camino máximo único que comienza en x con un borde de color α y alterna los colores de los bordes (el segundo borde tiene el color β , el tercer borde tiene el color α y así sucesivamente), su longitud puede ser 0 . Tenga en cuenta que si c es una coloración de borde adecuada (Δ+1) de G , entonces a cada vértice le falta un color con respecto a c .
Supongamos que no existe una coloración de borde (Δ+1) adecuada de G. Esto es equivalente a esta declaració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 en α , creando así un (Δ+1) adecuado . coloración de bordes de G de c . Al revés, si existe una coloración de borde (Δ+1) adecuada , entonces podemos eliminar xy , restringir la coloración y (1) tampoco se mantendrá.
Ahora, sean xy 0 ∈ E y c 0 una coloración de borde (Δ+1) adecuada de G − xy 0 y falte α en x con respecto a c 0 . Definimos y 0 ,..., y k como una secuencia máxima de vecinos de x tal que falta c 0 ( xy i ) en y i −1 con respecto a c 0 para todo 0 < i ≤ k .
Definimos los colorantes c 1 ,..., c k como
Entonces c i es una coloración de borde (Δ+1) adecuada de G − xy i debido a la definición de y 0 ,..., y k . Además, tenga en cuenta que los colores que faltan en x son los mismos con respecto a ci para todo 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 . Tenga en cuenta que β no puede faltar en x ; de lo contrario, podríamos extender fácilmente c k , por lo tanto, una arista con color β incide en x para todo c j . A partir de la maximalidad de k , existe 1 ≤ i < k tal que c 0 ( xy i ) = β . De la definición de c 1 ,..., c k esto 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 un borde 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 . Dado que P' está determinado de forma única y los bordes internos de P no cambian en c 0 ,..., c k , el camino P' usa los mismos bordes que P en orden inverso y visita y k . El borde 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 gráficos como de clase uno o clase dos, pero no proporcionan una clasificación completa. Por ejemplo, si los vértices de grado máximo Δ en un gráfico 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 gráficos son de clase uno. Es decir, en el modelo Erdős-Rényi de gráficos aleatorios, en el que todos los gráficos de n -vértices son igualmente probables, sea p ( n ) la probabilidad de que un gráfico de n -vértices extraído de esta distribución sea de clase uno; entonces p ( n ) se acerca a uno en el límite cuando n tiende al infinito. Para conocer límites más precisos sobre la velocidad a la que p ( n ) converge a uno, consulte Frieze et al. (1988).
Vizing (1965) demostró que un grafo plano es de clase uno si su grado máximo es al menos ocho. Por el contrario, observó que para cualquier grado máximo en el rango de dos a cinco, existen gráficos planos de clase dos. Para el grado dos, cualquier ciclo impar es un gráfico de este tipo, y para los grados tres, cuatro y cinco, estos gráficos se pueden construir a partir de sólidos platónicos reemplazando un solo borde por una trayectoria de dos bordes adyacentes.
En la conjetura del gráfico plano de Vizing , Vizing (1965) afirma que todos los gráficos planos simples con grado máximo seis o siete son de clase uno, cerrando el resto de casos posibles. De forma independiente, Zhang (2000) y Sanders y Zhao (2001) demostraron parcialmente la conjetura del gráfico plano de Vizing al mostrar que todos los gráficos planos con grado máximo siete son de clase uno. Así, el único caso de la conjetura que queda sin resolver es el de grado máximo seis. Esta conjetura tiene implicaciones para la conjetura de la coloración total .
Los grafos planos 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 (probado por Appel y Haken (1976)) sobre la coloración de vértices de gráficos planos es equivalente a la afirmación de que todo gráfico plano regular de 3 regulares sin puente es de clase uno (Tait 1880).
En 1969, Branko Grünbaum conjeturó que cada gráfico de 3 regulares 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 gráficos tal que cada cara de la incrustación es topológicamente un disco y tal que el gráfico dual de la incrustación es simple, sin bucles automáticos ni adyacencias múltiples. De ser cierto, esto sería una generalización del teorema de los cuatro colores, que Tait demostró que era equivalente a la afirmación de que los gráficos de 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 alto género. Con base en esta construcción, también demostró que es NP-completo saber si un gráfico incrustado poliédricamente 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 los gráficos de clase dos y utiliza como máximo un color más del necesario para todos los gráficos. Su algoritmo sigue la misma estrategia que la prueba original de Vizing de su teorema: comienza con un gráfico sin color y luego encuentra repetidamente una manera 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 un borde sin color en un gráfico parcialmente coloreado. El algoritmo de Misra y Gries puede interpretarse como la construcción de un pseudobosque dirigido P (un gráfico en el que cada vértice tiene como máximo un borde saliente) sobre los vecinos de u : para cada vecino p de u , el algoritmo encuentra un color c que es no utilizado por ninguno de los bordes incidentes con p , encuentra el vértice q (si existe) para el cual el borde uq tiene color c y agrega pq como un borde a P . Hay dos casos:
Con algunas estructuras de datos simples para realizar un seguimiento de los colores que se utilizan y están disponibles en cada vértice, la construcción de P y los pasos de cambio de color del algoritmo se pueden implementar en el 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 en uno el número de bordes coloreados, el tiempo total es O( mn ) .
En un informe técnico no publicado, Gabow et al. (1985) reivindicaron un límite de tiempo más rápido para el mismo problema de colorear con colores Δ + 1 .
Tanto en Gutin y Toft (2000) como en Soifer (2008), Vizing menciona que su trabajo fue motivado por un teorema de Shannon (1949) que muestra que los multigrafos se pueden colorear con como máximo (3/2)Δ colores. Aunque el teorema de Vizing es ahora material estándar en muchos libros de texto de teoría de grafos, Vizing tuvo problemas para publicar el resultado inicialmente, y su artículo aparece en una revista poco conocida, Diskret. Analiz . [7]
