An application of matching theory of edge-colourings (Q1923520): Difference between revisions
From MaRDI portal
ReferenceBot (talk | contribs) Changed an Item |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/0012-365x(96)89437-4 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2022269624 / rank | |||
Normal rank |
Latest revision as of 11:48, 30 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | An application of matching theory of edge-colourings |
scientific article |
Statements
An application of matching theory of edge-colourings (English)
0 references
11 March 1997
0 references
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.
0 references
matchings
0 references
multigraphs
0 references
edge-chromatic number
0 references