Vadim G. Vizing
Encyclopedia
Vadim Georgievich Vizing is a Ukrainian
(former Soviet) mathematician
known for his contributions to graph theory
, and especially for Vizing's theorem stating that the edges of any graph with maximum degree Δ can be colored
with at most Δ + 1 colors.
on March 25, 1937. His mother was half-German, 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. After holding various additional positions, he moved to Odessa
in 1974, where he taught mathematics for many years at the Academy for Food Technology.
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). 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.
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, 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.
Ukrainians
Ukrainians are an East Slavic ethnic group native to Ukraine, which is the sixth-largest nation in Europe. The Constitution of Ukraine applies the term 'Ukrainians' to all its citizens...
(former Soviet) mathematician
Mathematician
A mathematician is a person whose primary area of study is the field of mathematics. Mathematicians are concerned with quantity, structure, space, and change....
known for his contributions to graph theory
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
, and especially for Vizing's theorem stating that the edges of any graph with maximum degree Δ can be colored
Edge coloring
In graph theory, an edge coloring of a graph is an assignment of “colors” to the edges of the graph so that no two adjacent edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blue, and green. Edge colorings are one of several...
with at most Δ + 1 colors.
Biography
Vizing was born in KievKiev
Kiev or Kyiv is the capital and the largest city of Ukraine, located in the north central part of the country on the Dnieper River. The population as of the 2001 census was 2,611,300. However, higher numbers have been cited in the press....
on March 25, 1937. His mother was half-German, 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
Tomsk State University
Tomsk State University , formerly Imperial Tomsk University, is the first university in Siberia—it was founded in 1878 in Tomsk, Russia. TSU opened in 1888 with only one department, the medical school...
in 1959, he began his Ph.D. studies at the Steklov Institute of Mathematics
Steklov Institute of Mathematics
Steklov Institute of Mathematics or Steklov Mathematical Institute is a research institute based in Moscow, specialized in mathematics, and a part of the Russian Academy of Sciences. It was established April 24, 1934 by the decision of the General Assembly of the Academy of Sciences of the USSR in...
in Moscow
Moscow
Moscow is the capital, the most populous city, and the most populous federal subject of Russia. The city is a major political, economic, cultural, scientific, religious, financial, educational, and transportation centre of Russia and the continent...
, on the subject of function approximation
Function approximation
The need for function approximations arises in many branches of applied mathematics, and computer science in particular. In general, a function approximation problem asks us to select a function among a well-defined class that closely matches a target function in a task-specific way.One can...
, but he left in 1962 without completing his degree. Instead, he returned to Novosibirsk
Novosibirsk
Novosibirsk is the third-largest city in Russia, after Moscow and Saint Petersburg, and the largest city of Siberia, with a population of 1,473,737 . It is the administrative center of Novosibirsk Oblast as well as of the Siberian Federal District...
, working from 1962 to 1968 at the Russian Academy of Sciences
Russian Academy of Sciences
The Russian Academy of Sciences consists of the national academy of Russia and a network of scientific research institutes from across the Russian Federation as well as auxiliary scientific and social units like libraries, publishers and hospitals....
there and earning a Ph.D. in 1966. After holding various additional positions, he moved to Odessa
Odessa
Odessa or Odesa is the administrative center of the Odessa Oblast located in southern Ukraine. The city is a major seaport located on the northwest shore of the Black Sea and the fourth largest city in Ukraine with a population of 1,029,000 .The predecessor of Odessa, a small Tatar settlement,...
in 1974, where he taught mathematics for many years at the Academy for Food Technology.
Research results
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 coloredEdge coloring
In graph theory, an edge coloring of a graph is an assignment of “colors” to the edges of the graph so that no two adjacent edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blue, and green. Edge colorings are one of several...
using at most Δ + 1 colors. It is a continuation of the work of Claude Shannon, who showed that any multigraph
Multigraph
In mathematics, a multigraph or pseudograph is a graph which is permitted to have multiple edges, , that is, edges that have the same end nodes. Thus two vertices may be connected by more than one edge....
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). 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.
Vizing also made other contributions to graph theory and graph coloring, including the introduction of list coloring, the formulation of the total coloring
Total coloring
In graph theory, total coloring is a type of coloring on the vertices and edges of a graph.When used without any qualification, a total coloring is always assumed to be proper in the sense that no adjacent vertices, no adjacent edges, and no edge and its endvertices are assigned the same color.The...
conjecture (still unsolved) stating that the edges and vertices of any graph can together be colored with at most Δ + 2 colors, Vizing's conjecture
Vizing's conjecture
In graph theory, Vizing's conjecture concerns a relation between the domination number and the cartesian product of graphs.This conjecture was first stated by , and states that, if γ denotes the minimum number of vertices in a dominating set for G, then conjectured a similar bound for the...
(also unsolved) concerning the domination number of cartesian products of graphs
Cartesian product of graphs
In graph theory, the Cartesian product G \square H of graphs G and H is a graph such that* the vertex set of G \square H is the Cartesian product V × V; and...
, and the 1974 definition of the modular product of graphs
Modular product of graphs
In graph theory, the modular product of graphs G and H is a graph such that* the vertex set of the modular product of G and H is the cartesian product V × V; and...
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
Job Shop Scheduling
Job shop scheduling is an optimization problem in computer science in which ideal jobs are assigned to resources at particular times. The most basic version is as follows:...
instead, only returning to graph theory again in 1995.