# Coloring a graph with odd number of vertices with $k$ (which is close to $\Delta$) colors in linear time

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?

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.