We have an undirected simple connected graph with odd number of vertices. We also know the number $k$ which is actually the closest odd number greater than or equal to $\Delta$. (So if $\Delta$ is even, $k = \Delta +1$ else $k=\Delta$.) i.e $k$ is the least odd number that is greater than or equal to degrees of all vertices.
We want to find a linear time algorithm that colors the graph with $k$ colors.
I am very new to graph coloring algorithms. I know that a greedy algorithm is actually linear time and can color the graph with $\Delta +1$. But I can't guarantee I can color it with $k= \Delta$ when $\Delta$ is odd. Also, we probably should use all the information the question gives us. i.e using odd number of vertices somehow, but greedy algorithm don't use this extra information.
How can I solve this?