Coloring a graph with odd number of vertices with $k$ (which is close to $\Delta$) colors in linear time
Brooks' theorem states that every connected graph $G$ with maximum degree $\Delta$ can be colored (in linear time) using at most $\Delta + 1$ colors. In fact, the graphs that require $\Delta + 1$ colors are precisely complete graphs and odd cycles.

You state that we have a connected graph $G$ with an odd number of vertices and we want to color $G$ with $k$ colors, where $k = \Delta + 1$ when $\Delta$ is even and $k = \Delta$ otherwise. Let's break this down into cases:


$G$ is complete (i.e., $G$ is $K_n$ for $n = 3,5,7,\ldots$). By definition, $\Delta = n-1$ and since $n$ is odd, we have that $\Delta$ is even. Thus, we can color $G$ with $k = \Delta+1$ colors.
$G$ is a cycle (i.e., $G$ is $C_n$ for $n = 3,5,7,\ldots$). Clearly, for any non-trivial cycle we have that $\Delta = 2$ which is even. Again, we can color $G$ with $k = \Delta+1$ colors.
$G$ is not complete nor a cycle. By Brooks' theorem, we have that $\chi(G) \leq \Delta \leq k$, so we are done.