Визинг, Вадим Георгиевич

Вадим Георгиевич Визинг
Дата рождения	25 марта 1937(1937-03-25)
Место рождения	Киев, Украинская ССР, СССР
Дата смерти	23 августа 2017(2017-08-23)
Место смерти	Одесса
Страна	СССР →  Украина
Род деятельности	graph theorist, математик
Научная сфера	математика
Альма-матер	ТГУ

Вадим Георгиевич Визинг (25 марта 1937, Киев — 23 августа 2017, Одесса) — советский и украинский математик, известный благодаря исследованиям в теории графов, прежде всего — теореме Визинга.

Мать — наполовину немка, в связи с чем, по утверждению Визинга, семья была сослана в Сибирь в 1947 году. Окончил Томский государственный университет по специальности математика в 1959 году, после чего поступил в аспирантуру в Институте математики имени Стеклова в Москве, работал в области теории приближений, но покинул аспирантуру в 1962 году, не получив степень[1]. Вместо этого переехал в Новосибирск, где в Институте математики Сибирского отделения АН СССР защитил в 1966 году кандидатскую диссертацию[1]. В 1974 году переехал в Одессу, где преподавал математику в течение многих лет в Технологическом институте пищевой промышленности[1].

Результат, известный сейчас как теорема Визинга, опубликован в 1964 году во время работы в Новосибирске, утверждает, что рёбра произвольного графа с не более чем ${\displaystyle \Delta }$ рёбрами на вершину могут быть раскрашены не более чем ${\displaystyle \Delta +1}$ цветами[2]. Западными авторами считается, что Визинг имел трудности с публикацией результата, указывая на «малоизвестность» журнала «Дискретный анализ» (издававшегося Институтом математики СО АН СССР). Другой вклад в теорию графов — введение понятия списочного раскраса[3] и формулировка нерешённой по состоянию на 2017 год гипотезы тотального раскраса[4][5]. Гипотеза Визинга (сформулированная в 1974 году и также нерешённая) касается числа доминирования прямого произведения графов[4] и определения модулярного произведения графов как способа сведения задач изоморфизма подграфа для нахождения крупнейших клик в графах[6].

С 1976 года Визинг изучал задачи теории расписаний, вернувшись к теории графов вновь только в 1995 году[1].

Примечания

1. Гутин, Тофт, 2000.
2. В. Г. Визинг. Об оценке хроматического класса ${\displaystyle p}$-графа // Дискретный анализ : сборник. — Новосибирск: Институт математики СО АН СССР, 1964. — Т. 3. — С. 25–30.
3. Визинг В. Г. Раскраска вершин графа в предписанные цвета // Дискретный анализ. — 1976. — Т. 29. — С. 3—10.
4. В. Г. Визинг. Некоторые нерешенные задачи в теории графов // Успехи математических наук. — 1968. — Т. 23, вып. 6. — С. 117–134.
5. Визинг утверждает, что он сформулировал эту гипотезу в 1964 году, однако пока она была опубликована в 1968 году, Бехзад независимо выдвинул аналогичную гипотезу
6. Визинг В. Г. Сведение проблемы изоморфизма и изоморфного вхождения к задаче нахождения неплотности графа // Тез. Докл. III Всесоюз.конф. По проблемам теоретической кибернетики. — Новосибирск: ИМ СО АН СССР, 1974. — С. 124—125.

Литература

• Interview with Vadim G. Vizing // European Mathematical Society Newsletter. — 2000. — Т. 38, № December. — P. 22—23.
• Alexander Soifer. The Mathematical Coloring Book. — Springer-Verlag, 2008. — ISBN 9780387746401.. Страницы 136—137 воспроизводят письмо от 1995 года от Визинга к Сойферу относительно формулировки гипотезы тотального раскраска, также содержит некоторые биографические подробности о Визинге.