Vadim G. Vizing

Vadim Georgievich Vizing ( en ruso : Вади́м Гео́ргиевич Визинг , en ucraniano : Вадим Георгійович Візінг ; 25 de marzo de 1937 – 23 de agosto de 2017) ^{[ 1 ]} fue un matemático soviético y ucraniano conocido por sus contribuciones a la teoría de grafos , y especialmente por el teorema de Vizing que establece que las aristas de cualquier grafo simple con grado máximo Δ pueden colorearse con como máximo Δ + 1 colores.   

Vizing nació en Kiev el 25 de marzo de 1937. ^{[ 2 ] [ 3 ]} Su madre era medio alemana, y debido a esto las autoridades soviéticas obligaron a su familia a mudarse a Siberia en 1947. Después de completar sus estudios de pregrado en matemáticas en la Universidad Estatal de Tomsk en 1959, comenzó sus estudios de doctorado en el Instituto de Matemáticas Steklov en Moscú , sobre el tema de aproximación de funciones , pero lo dejó en 1962 sin completar su título. ^{[ 2 ]} En cambio, regresó a Novosibirsk , trabajando de 1962 a 1968 en la Academia Rusa de Ciencias allí y obteniendo un doctorado en 1966. ^{[ 2 ] [ 4 ]} En Novosibirsk, fue un participante regular en el seminario de AA Zykov sobre teoría de grafos. ^{[ 5 ]} Después de ocupar varios puestos adicionales, se mudó a Odessa en 1974, donde enseñó matemáticas durante muchos años en la Academia de Tecnología de los Alimentos ^{[ 2 ]} (originalmente conocida como Одесский технологический институт пищевой промышленности им. М. В. Ломоносова, "Instituto Tecnológico de la Industria Alimentaria de Odessa que lleva el nombre de Mikhail Lomonosov ").

El resultado ahora conocido como el teorema de Vizing , publicado en 1964, cuando Vizing trabajaba en Novosibirsk, establece que las aristas de cualquier grafo con como máximo Δ aristas por vértice pueden colorearse usando como máximo Δ  +  1 colores. ^[V64] Es una continuación del trabajo de Claude Shannon , quien demostró que cualquier multigrafo puede tener sus aristas coloreadas con como máximo (3/2)Δ colores (una cota ajustada, ya que un triángulo con Δ/2 aristas por lado requiere esta cantidad de colores). ^{[ 6 ] [ nota 1 ]} 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 sobre él aparece en una revista poco conocida, Diskret. Analiz . ^{[ nota 2 ]}

Vizing también hizo otras contribuciones a la teoría de grafos y coloración de grafos , incluyendo la introducción de la coloración de listas , ^[V76] la formulación de la conjetura de coloración total (aún sin resolver) que establece que las aristas y los vértices de cualquier grafo pueden ser coloreados juntos con como máximo Δ  +  2 colores, ^{[V68] [ nota 3 ]} la conjetura de Vizing (también sin resolver) sobre el número de dominación de productos cartesianos de grafos , ^[V68] y la definición de 1974 del producto modular de grafos como una forma de reducir los problemas de isomorfismo de subgrafos a encontrar cliques máximos en grafos. ^[V74] También demostró una versión más fuerte del teorema de Brooks que se aplica a la coloración de listas.

Desde 1976, Vizing dejó de trabajar en teoría de grafos y estudió problemas de planificación en su lugar, ^{[ 7 ]} volviendo a la teoría de grafos solo en 1995. ^{[ 2 ]}

• Gran Medalla de Plata del Instituto de Matemáticas del Departamento Siberiano de la Academia Rusa de Ciencias ^{[ 5 ]}

• Lista de publicaciones recientes de Vadim Vizing y mathnet.ru