Teorema de Vizing

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 los colores Δ, y grafos de "clase dos" para los que son necesarios los colores Δ + 1. 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. 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. El matemático indio R. P. Gupta descubrió el teorema de forma independiente mientras realizaba su doctorado (1965-1967).

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 from x la única ruta máxima que comienza en x con un borde de color α y alternando los colores de los bordes (el segundo borde tiene color β, el tercer borde tiene color α y así sucesivamente), su longitud puede ser 0. Tenga en cuenta que si c es una coloración de arista (Δ+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:

1) xy ▪ E y c arbitrariamente (Δ+1)-edge-coloring of G − xy y α de estar desaparecido x y β de estar desaparecido Sí. con respecto a c. Entonces el α/β- el camino de Sí. termina en x.

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 borde (Δ+1) adecuada de G a partir de c. A la inversa, si existe una coloración de aristas (Δ+1) adecuada, entonces podemos eliminar xy, restringir la coloración y (1) tampoco se cumplirá.

Ahora, sea xy₀ ∈ E y c₀ una coloración de arista (Δ+1) adecuada de G − xy₀ y α falte en x con respecto a c₀. Definimos y₀,...,y_k como una secuencia máxima de vecinos de x tal que c₀(xy_i) falta en y_i−1 con respecto a c₀ para todo 0 < i ≤ k.

Definimos los colorantes c₁,...,c_k como

c_i()xy_j)=c₀()xy_{j+ 1}) para todos 0 ≤ j c) i,

c_i()xy_i) no definido,

c_i()e)=c₀()e) de lo contrario.

Entonces c_i es una coloración de arista (Δ+1) adecuada de G − xy_i debido a la definición de y₀,...,y_k. Además, tenga en cuenta que los colores que faltan 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₀, 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. A partir de la maximalidad de k, existe 1 ≤ i < k tal que c₀(xy_i) = β. De la definición de c₁,...,c_k se cumple:

c₀()xy_i) c_i−1()xy_i) c_k()xy_i−1) = β

Sea P la ruta α/β 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−1x. Ahora, sea P' la ruta α/β 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 se modifican en c₀,...,c_k, la ruta P' utiliza 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 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.

Erdős & Wilson (1977) demostraron que casi todos los grafos son de clase uno. Es decir, en el modelo de grafos aleatorios de Erdős–Rényi, 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 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. 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 así 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 integrado es de clase uno.

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 el número de bordes coloreados en uno.

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 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 sea utilizado por ninguna de las aristas incidentes a p, encuentra el vértice q (si existe) para la cual la arista uq tiene color c, y agrega pq como arista a P. Hay dos casos:

• Si el pseudoforest P construido de esta manera contiene un camino desde v a un vértice w que no tiene bordes salientes en PEntonces hay un color c que está disponible tanto en u y w. Borde recolorante Uw con color c permite que los colores del borde restante sean cambiados un paso a lo largo de este camino: para cada vértice p en el camino, borde arriba toma el color que fue utilizado anteriormente por el sucesor de p en el camino. Esto conduce a una nueva coloración que incluye el borde uv.
• Si, por otro lado, el camino desde v en la pseudoforestación P conduce a un ciclo, w ser el vecino u en el que el camino se une al ciclo, c ser el color del borde Uw, y dejar d ser un color que no es utilizado por ninguno de los bordes en el vértice u. Luego intercambiar colores c y d en una cadena Kempe rompe el ciclo o el borde en el que el camino se une al ciclo, llevando al caso anterior.

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).

In an unpublished technical report, Gabow et al. (1985) claimed a faster ${\displaystyle O(m{\sqrt {n}\log n)}$ tiempo limitado para el mismo problema de coloración con Δ + 1 colores.

Tanto en Gutin & Toft (2000) como en Soifer (2008), Vizing menciona que su trabajo estuvo motivado por un teorema de Shannon (1949) que mostraba que los multigrafos podían colorearse 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 inicialmente para publicar el resultado, y su artículo al respecto aparece en una revista poco conocida, Diskret. Analiz.

• Teorema de Brooks relacionando colorantes de vértice al máximo grado

• Appel, K.; Haken, W. (1976), "Cada mapa plano es de cuatro colores", Boletín de la American Mathematical Society, 82 (5): 711–712, doi:10.1090/S0002-9904-1976-14122-5, MR 0424602.
• Diestel, Reinhard (2000), Graph Theory (PDF), Berlín, Nueva York: Springer-Verlag, págs. 103 a 104.
• Erdős, Paul; Wilson, Robin J. (1977), "Nota sobre el índice cromático de casi todos los gráficos" (PDF), Journal of Combinatorial Teoría, Serie B, 23 (2–3): 255–257, doi:10.1016/0095-8956(77)90039-9.
• Fournier, Jean-Claude (1973), "Colorations des arêtes d'un graphe", Cahiers du Centre d'Études de Recherche Opérationnelle, 15: 311–314, RM 0349458.
• Frieze, Alan M.; Jackson, B.; McDiarmid, C. J. H.; Reed, B. (1988), "Edge-colouring random graphs", Journal of Combinatorial Teoría, Serie B, 45 (2): 135-149, doi:10.1016/0095-8956(88)90065-2, MR 0961145.
• Gabow, Harold N.; Nishizeki, Takao; Kariv, Oded; Leven, Daniel; Terada, Osamu (1985), Algoritmos para gráficos de color de borde, Tech. Informe TRECIS-8501, Universidad de Tohoku.
• Gutin, Gregory; Toft, Bjarne (diciembre de 2000), "Entrevista con Vadim G. Vizing" (PDF), European Mathematical Society Newsletter, 38: 22–23.
• Kochol, Martin (2009), "Polyhedral embeddings of snarks in orientable surfaces", Proceedings of the American Mathematical Society, vol. 137, pp. 1613–1619.
• Kochol, Martin (2010), "Complejidad de 3-edge-coloring en la clase de gráficos cúbicos con una incrustación poliedral en una superficie orientable", Discreta Matemáticas aplicadas, 158 (16): 1856-1860, doi:10.1016/j.dam.2010.06.019, MR 2679785.
• Misra, J.; Gries, David (1992), "Una prueba constructiva del teorema de Vizing", Cartas de procesamiento de información, 41 (3): 131–133, doi:10.1016/0020-0190(92)90041-S.
• Sanders, Daniel P.; Zhao, Yue (2001), "Los gráficos planos del grado máximo siete son clase I", Journal of Combinatorial Teoría, Serie B, 83 (2): 201–212, doi:10.1006/jctb.2001.2047.
• Shannon, Claude E. (1949), "Un teorema para colorear las líneas de una red", J. Matemáticas, 28 (1–4): 148–151, doi:10.1002/sapm1949281148, MR 0030203.
• Soifer, Alexander (2008), The Mathematical Coloring Book, Springer-Verlag, pp. 136–137, ISBN 978-0-387-74640-1.
• Tait, P. G. (1880), "Observaciones sobre los colores de los mapas", Proc. R. Soc. Edimburgo, 10: 729, doi:10.1017/S0370164600044643.
• Vizing, V. G. (1964), "En una estimación de la clase cromática de un p-graph", Diskret. Analiz., 3: 25–30, MR 0180505.
• Vizing, V. G. (1965), "Critical graphs with given chromatic class", Metody Diskret. Analiz., 5: 9–17. (En ruso.)
• Zhang, Limin (2000), "Cada gráfico plano con el grado máximo 7 es de clase 1", Gráficos y Combinatoria, 16 (4): 467-495, doi:10.1007/s003730070009, S2CID 10945647.

• Prueba del teorema de Vizing en PlanetMath.