A new tool for proving Vizing's Theorem

Research output: Contribution to journalArticlepeer-review

Abstract

The known proofs of the famous theorem of Vizing on edge coloring of (multi)graphs are not long but sophisticated. The main goal of this note is to present an auxiliary (multi)digraph that simplifies and facilitates proofs of it. The secondary goal is to use the approach for proofs of Vizing's Adjacency Lemma and the Andersen-Goldberg Theorem.

Original languageEnglish (US)
Pages (from-to)1-3
Number of pages3
JournalDiscrete Mathematics
Volume326
Issue number1
DOIs
StatePublished - Jul 6 2014

Keywords

  • Adjacency Lemma
  • Critical graphs
  • Edge coloring

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'A new tool for proving Vizing's Theorem'. Together they form a unique fingerprint.

Cite this