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

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

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

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

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

Примечания

↑ .
В. Г. Визинг. Об оценке хроматического класса $p$ -графа // Дискретный анализ : сборник. — Новосибирск: Институт математики СО АН СССР, 1964. — Т. 3 . — С. 25–30 .
Визинг В. Г. Раскраска вершин графа в предписанные цвета // Дискретный анализ. — 1976. — Т. 29 . — С. 3—10 .
↑ В. Г. Визинг. Некоторые нерешенные задачи в теории графов // Успехи математических наук. — 1968. — Т. 23 , вып. 6 . — С. 117–134 .
Визинг утверждает, что он сформулировал эту гипотезу в 1964 году, однако пока она была опубликована в 1968 году, Бехзад независимо выдвинул аналогичную гипотезу
Визинг В. Г. Сведение проблемы изоморфизма и изоморфного вхождения к задаче нахождения неплотности графа // Тез. Докл. 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 года от Визинга к Сойферу относительно формулировки гипотезы тотального раскраска, также содержит некоторые биографические подробности о Визинге.