𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A short proof for a generalization of Vizing's theorem

✍ Scribed by Claude Berge; Jean Claude Fournier

Publisher
John Wiley and Sons
Year
1991
Tongue
English
Weight
183 KB
Volume
15
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

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.

📜 SIMILAR VOLUMES

A Short Proof of Mader's S-Paths Theorem
A Short Proof of Mader's S-Paths Theorem
✍ Alexander Schrijver 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 78 KB

For an undirected graph G=(V, E) and a collection S of disjoint subsets of V, an S-path is a path connecting different sets in S. We give a short proof of Mader's min-max theorem for the maximum number of disjoint S-paths. 2001

A short proof of K�nig's matching theore
A short proof of K�nig's matching theorem
✍ Rizzi, Romeo 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 43 KB 👁 2 views

We give a short proof of the following basic fact in matching theory: in a bipartite graph the maximum size of a matching equals the minimum size of a node cover.

A generalization of Turán's theorem
A generalization of Turán's theorem
✍ Benny Sudakov; Tibor Szabó; H. Van Vu 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 94 KB

## Abstract In this paper, we obtain an asymptotic generalization of Turán's theorem. We prove that if all the non‐trivial eigenvalues of a __d__‐regular graph __G__ on __n__ vertices are sufficiently small, then the largest __K__~__t__~‐free subgraph of __G__ contains approximately (__t__ − 2)/(__

A short proof of a theorem of dirac's ab
A short proof of a theorem of dirac's about hadwiger's conjecture
✍ D. R. Woodall 📂 Article 📅 1992 🏛 John Wiley and Sons 🌐 English ⚖ 105 KB 👁 1 views

## Abstract A Short proof is given of the theorem that every grph that does not have __K__~4~ as a subcontraction is properly vertex 3‐colorable.