A constructive proof of Vizing’s theorem. (English) Zbl 0795.68157

The proof of Vizing’s theorem given in this note is essentially the same proof given by Vizing [see S. Fiorini and R. J. Wilson: Edge- colourings of graphs, Pitman (1977; Zbl 0421.05023), pp. 30-32]. There are some ambiguities/gaps in the description of the process for “Inversting the cd-path of \(X\)” in this note. Vizing’s theorem has been generalized by L. D. Andersen and also by M. K. Gol’dberg [see the reviewer’s book: Some topics in graph theory, Cambridge University Press (1986; Zbl 0588.05002), pp. 14-16].


68R10 Graph theory (including graph drawing) in computer science
68Q60 Specification and verification (program logics, model checking, etc.)
05C15 Coloring of graphs and hypergraphs
Full Text: DOI


[1] Bollobás, B., Graph Theory (1979), Springer: Springer New York · Zbl 0418.05049
[2] Dijkstra, E. W.; Rao, J. R., Designing the proof of Vizing’s algorithm, (EWD1082a (September 1990), University of Texas at Austin)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.