An application of matching theory of edge-colourings
type: Item
instance of: scholarly article
title: An application of matching theory of edge-colourings
zbMATH Open document ID: 0858.05042
DOI: 10.1016/0012-365X(96)89437-4
author: J. Griggs
author: R. P. Anstee
published in: Discrete Mathematics
publication date: 1997-03-11T00:00:00Z
review text: The authors use a result about matchings in multigraphs to obtain a short, natural proof of a result of \textit{C. E. Shannon} [J. Math. Phys., Massachusetts 28, 148-151 (1949; Zbl 0032.43203)] that the edge-chromatic number of a finite, loopless multigraph is bounded above by 3/2 times the maximum degree. They also give a counterexample to the conjecture of \textit{L. Lovász} and \textit{M. D. Plummer} [Matching theory (1986; Zbl 0618.05001)] that for every simple graph for which the subgraph induced by the vertices of maximum degree is bipartite, the edge-chromatic number equals the maximum degree.
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C70
zbMATH DE Number: 932562
zbMATH Keywords: matchings
zbMATH Keywords: multigraphs
zbMATH Keywords: edge-chromatic number
reviewed by: Arthur T. White
MaRDI profile type: Publication
cites work: Simplified existence theorems for \((g,f)\)-factors
cites work: Q4018552
cites work: A short proof for a generalization of Vizing's theorem
cites work: Q5422499
cites work: A new method of proving theorems on chromatic index
cites work: Q4200237
cites work: Matching theory
cites work: A Theorem on Coloring the Lines of a Network
full work available at URL: 0012-365x(96)89437-4
OpenAlex ID: W2022269624
description: scientific article; zbMATH DE number 932562