théorème de Vizing

COMBINATOIRE

Dans le cadre de la théorie des graphes, le théorème de Vizing est un théorème de coloration.
Il énonce que la coloration des arêtes d’un graphe G peut s’effectuer à l’aide de Δ+1 couleurs au maximum, où Δ est le degré maximal du graphe G.
Ce théorème, publié en 1964, est dû au mathématicien soviétique et ukrainien Vadim G. Vizing (1937 – 2017).