Vizing

Vizing is a Russian mathematician known for his contributions to graph theory, particularly in the area of edge coloring. He is best known for proving what is now called Vizing's theorem, a foundational result in the theory of edge coloring that has influenced subsequent research in the field.

Vizing's theorem states that for every simple graph G, the edge chromatic number χ'(G) is at most Δ(G) + 1, where Δ(G) is the maximum degree of G. Consequently, χ'(G) ∈ {Δ(G), Δ(G) + 1}. Graphs with χ'(G) = Δ(G) are called class 1, while those with χ'(G) = Δ(G) + 1 are class 2. The theorem implies that the edges of any simple graph can be colored with at most Δ(G) + 1 colors so that no two adjacent edges share a color. The bound is tight; there exist graphs for which χ'(G) = Δ(G) + 1.

Since its introduction, Vizing's theorem has become a central result in graph theory and has inspired extensive further research, including attempts to characterize class 1 and class 2 graphs and generalizations to multigraphs and list edge-colorings. The theorem remains a cornerstone of the study of edge coloring and has applications in scheduling, frequency assignment, and other combinatorial optimization problems.