(Δ-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 ) ⩾ 10 14 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.