An application of matching theory of edge-colourings (Q1923520): Difference between revisions

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.