Vadim Georgievich Vizing (, ; 25 March 1937 – 23 August 2017) was a

Soviet The Union of Soviet Socialist Republics. (USSR), commonly known as the Soviet Union, was a List of former transcontinental countries#Since 1700, transcontinental country that spanned much of Eurasia from 1922 until Dissolution of the Soviet ...

and Ukrainian

mathematician A mathematician is someone who uses an extensive knowledge of mathematics in their work, typically to solve mathematical problems. Mathematicians are concerned with numbers, data, quantity, mathematical structure, structure, space, Mathematica ...

known for his contributions to

graph theory In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...

, and especially for

Vizing's theorem In graph theory, Vizing's theorem states that every simple undirected graph may be edge colored using a number of colors that is at most one larger than the maximum degree of the graph. At least colors are always necessary, so the undirected gr ...

stating that the edges of any simple graph with maximum degree Δ can be

colored ''Colored'' (or ''coloured'') is a racial descriptor historically used in the United States during the Jim Crow era to refer to an African American. In many places, it may be considered a slur. Dictionary definitions The word ''colored'' wa ...

with at most Δ + 1 colors.

Biography

Vizing was born in

Kiev Kyiv, also Kiev, is the capital and most populous List of cities in Ukraine, city of Ukraine. Located in the north-central part of the country, it straddles both sides of the Dnieper, Dnieper River. As of 1 January 2022, its population was 2, ...

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 The National Research Tomsk State University, TSU () is a public research university located in Tomsk, Russia. The university, which opened in 1888, was the first university in the Asian part of Russia and, in practice, the first Russian univ ...

in 1959, he began his Ph.D. studies at the

Steklov Institute of Mathematics Steklov Institute of Mathematics or Steklov Mathematical Institute () is a premier research institute based in Moscow, specialized in mathematics, and a part of the Russian Academy of Sciences. The institute is named after Vladimir Andreevich Stek ...

Moscow Moscow is the Capital city, capital and List of cities and towns in Russia by population, largest city of Russia, standing on the Moskva (river), Moskva River in Central Russia. It has a population estimated at over 13 million residents with ...

, on the subject of

function approximation In general, a function approximation problem asks us to select a function (mathematics), function among a that closely matches ("approximates") a in a task-specific way. The need for function approximations arises in many branches of applied ...

, but he left in 1962 without completing his degree. Instead, he returned to

Novosibirsk Novosibirsk is the largest city and administrative centre of Novosibirsk Oblast and the Siberian Federal District in Russia. As of the 2021 Russian census, 2021 census, it had a population of 1,633,595, making it the most populous city in Siber ...

, working from 1962 to 1968 at the

Russian Academy of Sciences The Russian Academy of Sciences (RAS; ''Rossíyskaya akadémiya naúk'') consists of the national academy of Russia; a network of scientific research institutes from across the Russian Federation; and additional scientific and social units such ...

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 ODESSA is an American codename (from the German language, German: ''Organisation der ehemaligen SS-Angehörigen'', meaning: Organization of Former SS Members) coined in 1946 to cover Ratlines (World War II aftermath), Nazi underground escape-pl ...

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 Mikhail Vasilyevich Lomonosov (; , ; – ) was a Russian polymath, scientist and writer, who made important contributions to literature, education, and science. Among his discoveries were the atmosphere of Venus and the law of conservation of ...

").

Research results

The result now known as

, published in 1964, when Vizing was working in Novosibirsk, states that the edges of any graph with at most Δ edges per vertex can be

using at most Δ + 1 colors. It is a continuation of the work of

Claude Shannon Claude Elwood Shannon (April 30, 1916 – February 24, 2001) was an American mathematician, electrical engineer, computer scientist, cryptographer and inventor known as the "father of information theory" and the man who laid the foundations of th ...

, who showed that any

multigraph In mathematics, and more specifically in graph theory, a multigraph is a graph which is permitted to have multiple edges (also called ''parallel edges''), that is, edges that have the same end nodes. Thus two vertices may be connected by mor ...

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).In both and , Vizing mentions that his work was motivated by Shannon's theorem. For the triangle lower bound example, see e.g
Colorful Mathematics
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''.The full name of this journal was ''Akademiya Nauk SSSR. Sibirskoe Otdelenie. Institut Matematiki. Diskretny˘ı Analiz. Sbornik Trudov''. It was renamed ''Metody Diskretnogo Analiza'' in 1980 (the name given for it in ) and discontinued in 199

Vizing also made other contributions to graph theory and

graph coloring In graph theory, graph coloring is a methodic assignment of labels traditionally called "colors" to elements of a Graph (discrete mathematics), graph. The assignment is subject to certain constraints, such as that no two adjacent elements have th ...

, including the introduction of

list coloring In graph theory, a branch of mathematics, list coloring is a type of graph coloring where each vertex can be restricted to a list of allowed colors. It was first studied in the 1970s in independent papers by Vizing and by Erdős, Rubin, and T ...

, the formulation of the

total coloring In graph theory, total coloring is a type of graph 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 edges, no adjacent vertices ...

conjecture (still unsolved) stating that the edges and vertices of any graph can together be colored with at most Δ + 2 colors,In , Vizing states that he formulated the conjecture in 1964, but by the time it was published in 1968 Behzad had independently posed the same 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 fo ...

(also unsolved) concerning the

domination number Domination or dominant may refer to: Society * World domination, structure where one dominant power governs the planet * Colonialism in which one group (usually a nation) invades another region for material gain or to eliminate competition * Ch ...

of cartesian products of graphs, and the 1974 definition of the

modular product of graphs In graph theory, the modular product of graphs and is a graph formed by combining and that has applications to subgraph isomorphism. It is one of several different kinds of graph products that have been studied, generally using the same ver ...

as a way of reducing

subgraph isomorphism The term subgraph can refer to: *The security-focused Linux-based Subgraph operating system, see Subgraph (operating system) *Subgraph of a function, see Hypograph (mathematics) *In graph theory In mathematics and computer science, graph theo ...

problems to finding

maximum clique In graph theory, a clique ( or ) is a subset of vertices of an undirected graph such that every two distinct vertices in the clique are adjacent. That is, a clique of a graph G is an induced subgraph of G that is complete. Cliques are one of th ...

s 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 A schedule (, ) or a timetable, as a basic time-management tool, consists of a list of times at which possible tasks, events, or actions are intended to take place, or of a sequence of events in the chronological order in which such things ...

instead, only returning to graph theory again in 1995.

Awards

*Great Silver Medal of the Institute of Mathematics of the Siberian Department of the Russian Academy of Sciences

Selected publications

Notes

References

External links

List of recent publications of Vadim Vizing
and mathnet.ru {{DEFAULTSORT:Vizing, Vadim G. 1937 births 2017 deaths Ukrainian mathematicians Soviet mathematicians Russian mathematicians Graph theorists Scientists from Kyiv Tomsk State University alumni Russian people of German descent Ukrainian people of German descent