Vadim Georgievich Vizing (Russian: Вади́м Гео́ргиевич Визинг, Ukrainian: Вадим Георгійович Візінг; 25 March 1937 – 23 August 2017) was a Soviet and Ukrainian mathematician known for his contributions to graph theory, and especially for Vizing's theorem stating that the edges of any simple graph with maximum degree Δ can be colored with at most Δ + 1 colors.
Vizing was born in Kiev on March 25, 1937. His mother was half-German,[1] and because of this the Soviet authorities forced his family to move to Siberia in 1947. After completing his undergraduate studies in mathematics in Tomsk State University in 1959, he began his Ph.D. studies at the Steklov Institute of Mathematics in Moscow, on the subject of function approximation, but he left in 1962 without completing his degree. Instead, he returned to Novosibirsk, working from 1962 to 1968 at the Russian Academy of Sciences there and earning a Ph.D. in 1966. In Novosibirsk, he was a regular participant in A. A. Zykov's seminar in graph theory. After holding various additional positions, he moved to Odessa in 1974, where he taught mathematics for many years at the Academy for Food Technology (originally known as Одесский технологический институт пищевой промышленности им. М. В. Ломоносова, "Odessa Technological Institute of Food Industry named after Mikhail Lomonosov").
The result now known as Vizing's theorem, published in 1964, when Vizing was working in Novosibirsk, states that the edges of any graph with at most Δ edges per vertex can be colored using at most Δ + 1 colors. It is a continuation of the work of Claude Shannon, who showed that any multigraph can have its edges colored with at most (3/2)Δ colors (a tight bound, as a triangle with Δ/2 edges per side requires this many colors).[2] Although Vizing's theorem is now standard material in many graph theory textbooks, Vizing had trouble publishing the result initially, and his paper on it appears in an obscure journal, Diskret. Analiz.[3]
Vizing also made other contributions to graph theory and graph coloring, including the introduction of list coloring, the formulation of the total coloring conjecture (still unsolved) stating that the edges and vertices of any graph can together be colored with at most Δ + 2 colors,[4] Vizing's conjecture (also unsolved) concerning the domination number of cartesian products of graphs, and the 1974 definition of the modular product of graphs as a way of reducing subgraph isomorphism problems to finding maximum cliques in graphs. He also proved a stronger version of Brook's theorem that applies to list coloring.
From 1976, Vizing stopped working on graph theory and studied problems of scheduling instead, only returning to graph theory again in 1995.