Premium
A short proof for a generalization of Vizing's theorem
Author(s) -
Berge Claude,
Fournier Jean Claude
Publication year - 1991
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190150309
Subject(s) - lemma (botany) , mathematics , combinatorics , constructive proof , simple graph , generalization , constructive , degree (music) , graph , discrete mathematics , transformation (genetics) , list coloring , simple (philosophy) , computer science , line graph , graph power , philosophy , process (computing) , mathematical analysis , chemistry , acoustics , biology , operating system , biochemistry , epistemology , physics , poaceae , gene , ecology
For a simple graph of maximum degree Δ, it is always possible to color the edges with Δ + 1 colors (Vizing); furthermore, if the set of vertices of maximum degree is independent, Δ colors suffice (Fournier). In this article, we give a short constructive proof of an extension of these results to multigraphs. Instead of considering several color interchanges along alternating chains (Vizing, Gupta), using counting arguments (Ehrenfeucht, Faber, Kierstead), or improving nonvalid colorings with Fournier's Lemma, the method of proof consists of using one single easy transformation, called “sequential recoloring”, to augment a partial k ‐coloring of the edges.