TY - JOUR

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

AU - Chetwynd, Amanda G.

AU - Hilton, A. J. W.

PY - 1990/2

Y1 - 1990/2

N2 - 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.

AB - 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.

U2 - 10.1016/0095-8956(90)90129-N

DO - 10.1016/0095-8956(90)90129-N

M3 - Journal article

VL - 48

JO - Journal of Combinatorial Theory, Series B

JF - Journal of Combinatorial Theory, Series B

SN - 0095-8956

IS - 1

ER -