(Δ-k)-critical graphs

Every graph G of maximum degree Δ is (Δ+1)-colourable and a classical theorem of Brooks states that G is not Δ-colourable iff G has a (Δ+1)-clique or Δ=2 and G has an odd cycle. Reed extended Brooks' Theorem by showing that if Δ(G)⩾1014 then G is not (Δ-1)-colourable iff G contains a Δ-clique. We extend Reed's characterization of (Δ-1)-colourable graphs and characterize (Δ-2), (Δ-3), (Δ-4) and (Δ-5)-colourable graphs, for sufficiently large Δ, and prove a general structure for graphs with χ close to Δ. We give a linear time algorithm to check the (Δ-k)-colourability of a graph, for sufficiently large Δ and any constant k.