A new method of proving theorems on chromatic index

A. Ehrenfeucht, V. Faber, H. A. Kierstead

Research output: Contribution to journalArticlepeer-review

12 Scopus citations


V.G. Vizing proved that the edge-chromatic number x1 of any multigraph M with maximum degree Δ(M) and maximum multiplicity μ(M) is Δ(M)+μ(M). In this paper we present a new method for proving this and other related results that are due to Gol'dberg, Anderson, Ore, Shannon, and Vizing. In our proofs we replace arguments about 'fan sequences' with counting arguments.

Original languageEnglish (US)
Pages (from-to)159-164
Number of pages6
JournalDiscrete Mathematics
Issue number2-3
StatePublished - 1984
Externally publishedYes

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'A new method of proving theorems on chromatic index'. Together they form a unique fingerprint.

Cite this