Home > Research > Publications & Outputs > The chromatic index of graphs with large maximu...
View graph of relations

The chromatic index of graphs with large maximum degree, where the number of vertices of maximum degree is relatively small.

Research output: Contribution to Journal/MagazineJournal article

Published
<mark>Journal publication date</mark>02/1990
<mark>Journal</mark>Journal of Combinatorial Theory, Series B
Issue number1
Volume48
Publication StatusPublished
<mark>Original language</mark>English

Abstract

By Vizing's theorem, the chromatic index χ′(G) of a simple graph G satisfies Δ(G) ≤ χ′(G) ≤ Δ(G) + 1; if χ′(G) = Δ(G), then G is Class 1, and if χ′(G) = Δ(G) + 1, then G is Class 2. We describe the structure of Class 2 graphs satisfying the inequality , where r is the number of vertices of maximum degree. A graph G is critical if G is Class 2 and χ′(H) < χ′(G) for all proper subgraphs H of G. We also describe the structure of critical graphs satisfying the inequality above. We also deduce, as a corollary, an earlier result of ours that a regular graph G of even order satisfying is Class 1.