(\(\Delta-k\))-critical graphs (Q1767668)

The paper contains a characterisation of \((\Delta-2),(\Delta-3), (\Delta-4)\) and \((\Delta-5)\)-colourable graphs for a sufficiently large value of \(\Delta\) (where \(\Delta\) is the maximum degree of a graph). These results extend a classical result of \textit{R. L. Brooks} [Proc. Camb. Philos. Soc. 37, 194--197 (1941; Zbl 0027.26403)] on \(\Delta\) and \(\Delta+1\)-colourable graphs and a characterisation of \(\Delta-1\)-colourable graphs by \textit{B. Reed} [J. Comb. Theory, Ser. B 76, 136--149 (1999; Zbl 0935.05045)]. Moreover a linear time algorithm for checking the \((\Delta-k)\)-colourability, for sufficiently large \(\Delta\) and any constant \(k\), is provided.