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

Question

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?

Answer 1

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.