The result mentioned in the question can be obtained by a chain of two standard reductions. The simplest reduction for $k$-COLORABILITY $\leq_p$ $(k+1)$-COLORABILITY (namely, adding a universal vertex) is clearly a linear reduction.
Also, the reduction $k$-COLORABILITY $\leq_p$ $k$-COLORABILITY($\Delta\leq k-1+\lceil \sqrt{k} \rceil$) given by Emden-Weinert et al. [2] is a linear reduction.
From these observations, it follows that, unless ETH fails, there is no $2^{o(n)}$-time algorithm for $k$-COLORABILITY($\Delta\leq k-1+\lceil \sqrt{k} \rceil$), .
Detailed Explanation:
Let $G$ be a graph of maximum degree $4$ as constructed in the hardness result of Cygan et al [1].
Add $k-4$ new vertices to $G$ and connect them to all vertices of $G$ as well as to themselves, the resulting graph $G'$ has an unbounded degree but, all except $k-4$ of the vertices has degree at most $k$. We do not know whether $G'$ is $k$-colorable. The number of newly added edges and vertices for a constant $k$ is $O(n)$, thus any $2^{o(n)}$ algorithm for $k$-coloring of $G'$ falsifies ETH.
The second step is to reduce the maximum degree of $G'$ by the method provided in the work of Emden-Weinert et al. [2]. Their method roughly speaking is as follows: they take a high degree vertex $u$ then remove $k$ edges of $u$ and add $k-1$ new edges to $u$ to connect it to a specific gadget with $O(k)$ many vertices. This procedure clearly reduces the degree of $u$ by one, and if we repeat this process $n-k$ times, the degree of $u$ will be at most $k$. They showed that the newly created graph after this step exhibits a similar coloring scheme as the original graph (except for the gadgets). As long as there is a high degree vertex, they repeat the mentioned degree reduction procedure. Additionally, based on their construction, we know that the maximum degree of vertices inside gadgets is at most $k-1+\lceil \sqrt{k} \rceil$, thus once the procedure ends, the resulting graph has the claimed maximum degree.
Observe that we have to perform the aforementioned procedure only on $k$ vertices of $G'$ and since their degree is $n+k-4$, after at most $O(kn)$ iterations the procedure stops. Additionally in each iteration, we add at most $O(k)$ new vertices, which means by the end of the procedure, the constructed graph has at most $O(k^2n)$ vertices. Hence, any $2^{o(k^2n)}$ algorithm for $k$-coloring of this graph, would result in a $2^{o(n)}$ algorithm for $3$-coloring of the input graph $G$. Since $k$ is a fixed constant, we conclude that any $2^{o(n)}$ algorithm for k-coloring on this graph would lead us to a $2^{o(n)}$ algorithm for $3$-coloring of $G$.
