THE CHROMATIC INDEX OF GRAPHS WITH LARGE MAXIMUM DEGREE, WHERE THE NUMBER OF VERTICES OF MAXIMUM DEGREE IS RELATIVELY SMALL

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 Δ(G) ≥ ⌊ 1 2|V(G)|⌋ + 7 2r, 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 d(G) ≥ 6 7|V(G)| is Class 1. © 1990.