Vadim G. Vizing

Vizing est né à Kiev le 25 mars 1937[3]^,[4]. Sa mère était pour moitié d'origine allemande[note 1] et pour cette raison les autorités soviétiques ont obligé sa famille à déménager en Sibérie en 1947. Vizing termine ses études de premier cycle en mathématiques à l'université d'État de Tomsk en 1959, puis il commence un doctorat à l'Institut de mathématiques Steklov à Moscou, sur le thème de l'approximation des fonctions, mais ce sujet ne l’intéresse guère et il quitte l'Institut en 1962 sans avoir obtenu son diplôme[3]. Il retourne à Novossibirsk et travaille de 1962 à 1968 à l'Académie des sciences de Russie où il obtient un doctorat en 1966[3]^,[5] sous la direction sinon officielle, du moins effective de A. A. Zykov[3]. À Novossibirsk, il est un participant régulier au séminaire de A. A. Zykov en théorie des graphes[6]. Après avoir occupé divers autres postes, il part pour Odessa en 1974, où il enseigne les mathématiques pendant de nombreuses années à l'Académie de technologie alimentaire [3] (connue au début sous le nom de Одесский технологический институт пищевой промышленности им. М. В. Ломоносова, Institut technologique d'Odessa de l'industrie alimentaire qui porte le nom de Mikhaïl Lomonossov). con

Le résultat maintenant connu sous le nom de théorème de Vizing, publié en 1964 lorsque Vizing travaillait à Novossibirsk, indique que les arêtes de tout graphe avec au plus Δ arêtes par sommet peuvent être colorées en utilisant au plus Δ + 1 couleurs[7]. Il s'agit d'une continuation du travail de Claude Shannon, qui a montré que tout multigraphe peut avoir ses arêtes colorées avec au plus (3/2) Δ couleurs (cette borne est atteinte puisqu'un triangle avec Δ / 2 arêtes par côté exige ce nombre de couleurs)[8]. Le théorème de Vizing est maintenant un thème standard dans de nombreux manuels de théorie des graphes, mais Vizing avait du mal à publier le résultat et son article sur ce sujet apparaît dans un journal peu connu : Diskret. Analiz..

Vizing a également apporté d'autres contributions à la théorie des graphes et à la coloration des graphes, y compris l'introduction de la coloration de liste[9], la formulation de la conjecture de coloration totale (toujours non résolue) indiquant que les arêtes et les sommets de tout graphe peuvent être colorés ensemble avec au plus Δ + 2 couleurs, [10]. La conjecture de Vizing (également non résolue) concernant la taille d'un ensemble dominant dans les produits cartésiens de graphes[10] et la définition en 1974 du produit modulaire des graphes comme moyen de réduire les problèmes d'isomorphisme des sous-graphes à la recherche de cliques maximales dans les graphes[11]. Il a également prouvé une version plus forte du théorème de Brooks qui s'applique à la coloration des listes.

À partir de 1976, Vizing a cessé de travailler en théorie des graphes pour étudier des problèmes d'ordonnancement[12] ; il ne revient à la théorie des graphes qu'en 1995[3].

• Grande médaille d'argent de l'Institut de mathématiques du département sibérien de l'Académie russe des sciences [6]

• (ru) Vadim Vizing, « On an estimate of the chromatic class of a p-graph », Diskret. Analiz., vol. 3,‎ 1964, p. 25–30 (Math Reviews 0180505)
• (ru) Vadim Vizing, « Some unsolved problems in graph theory », Uspekhi Mat. Nauk, vol. 23, n^o 6,‎ 1968, p. 117–134 (Math Reviews 0240000)
• Vadim Vizing, « Reduction of the problem of isomorphism and isomorphic entrance to the task of finding the nondensity of a graph », Proc. 3rd All-Union Conf. Problems of Theoretical Cybernetics,‎ 1974, p. 124
• (ru) Vadim Vizing, « Vertex colorings with given colors », Diskret. Analiz., vol. 29,‎ 1976, p. 3–10

• Ressources relatives à la recherche :
  • (en) Digital Bibliography & Library Project
  • (en) Mathematics Genealogy Project

• Portail des mathématiques
• Portail de l'informatique théorique