Suppose we have a graph $G$ with maximum degree $\Delta$. Deciding if $G$ can be colored with $\Delta$ colors is easy: Brooks' theorem says that this is always possible, unless $G$ is a clique or an odd cycle.
I'm interested in the complexity of coloring $G$ with $(\Delta-1)$ colors. It is well-known that the case $\Delta=4$ is NP-complete, as NP-completeness of 3-coloring graphs of maximum degree 4 is already mentioned in Garey&Johnson's book. I would like to know if similar results are known for other small values of $\Delta$. For example, I tried searching for the complexity of $4$-coloring graphs of maximum degree $5$, but failed to find anything relevant.
Question: For which fixed values of $\Delta$ is the complexity of $(\Delta-1)$-coloring graphs of maximum degree $\Delta$ known?
Motivation: I would have initially thought that, since this is NP-hard for $\Delta=4$, it would be NP-hard for all larger values of $\Delta$. However, it turns out that this is false! According to the main result of [1], "for sufficiently large $\Delta$, any graph with maximum degree at most $\Delta$ and no cliques of size $\Delta$ has a $\Delta−1$ colouring". This implies that for sufficiently large (fixed) $\Delta$, the problem is in P by the following simple algorithm: check (in time $n^{\Delta}$) if $G$ contains a clique of size $\Delta$; if it does say NO, otherwise say YES.
Question The above implies that $(\Delta-1)$-coloring graphs of max degree $\Delta$ is in P for sufficiently large $\Delta$. What is the smallest concrete value of $\Delta$ for which this problem is known to be in P?
References: [1] A Strengthening of Brooks' Theorem, Bruce Reed, JCTB 1999. https://doi.org/10.1006/jctb.1998.1891
