A Constructive Proof of Vizing's Theorem

By J. Misra, D. Gries. 1992

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

1. Jianyu Wang
2. Gauri Joshi
3. Anit Kumar Sahu
4. Zhouyi Yang
5. Soummya Kar
6. Farzin Haddadpour
7. Xiang Li
8. Othmane Marfoq

Citations in the corpus

• MATCHA: Speeding Up Decentralized SGD via Matching Decomposition Sampling (2019, background): “For example, the polynomial-time edge coloring algorithm in [17], provably guarantees that the number of matchings M equals to either ∆( ) or ∆( ) + 1 , where ∆( ) is the maximal node degree.”
• The Algorithm Design Manual (2020, unknown): “Misra and Gries give a simple constructive proof of this result [MG92].”