Let $v$ be a vertex in a connected graph $G=(V,E)$ and let $G_r$ denote the subgraph of $G$ induced by the vertices at the distance exactly $r$ from $v$ (for all $r\geq 0$). Proove that $$\chi(G)\leq \max_r (\chi(G_r)+\chi(G_{r+1}))$$
I have this hint: Fix an optimal coloring of each of the graphs $G_r$ and use induction on the number of nonempty graphs $G_r$.
Any ideas how to do this? Can someone give me some additional hints?
Let $r$ be the number such that $\chi(G_r)+\chi(G_{r+1})$ is a maximum, and let $H$ be the subgraph of $G$ induced by the vertices of $G_r\cup G_{r+1}.$ We can color $H$ with $\chi(G_r)+\chi(G_{r+1})$ colors by coloring $G_r$ with $\chi(G_r)$ colors $C_r$ and coloring $G_{r+1}$ with $\chi(G_{r+1})$ colors $C_{r+1},$ where $C_r\cap C_{r+1} = \emptyset.$
By the definition of $r$, $\chi(G_{r+2}) \le \chi(G_r),$ so we can use $C_r$ to color $G_{r+2}.$ There can be no edge joining a vertex $x \in G_r$ to a vertex $y \in G_{r+2},$ for then there would be a path of length $r+1$ from $v$ to $y$. Similarly, we can use $C_{r+1}$ to color $G_{r-1}.$
Originally, I had thought we could just use $C_x$ to color all $G_s$ with $s\equiv x \pmod 2$ for $x\in \{r, r+1\},$ but that doesn't quite work. For example, suppose $r=4.$ We know that we can use $C_4$ to color $G_6$ and we know that $\chi(G_6)+\chi(G_7)\le \chi(G_4)+\chi(G_5),$ but it doesn't follow that $\chi(G_7)\le\chi(G_5),$ because $\chi(G_6)$ might be very small. In that case, we can use $\chi(G_6)$ colors from $C_4$ to color $G_6,$ and use the leftover colors from $C_4$ together with the colors from $C_5$ to color $G_7$. Now we have to worry about $G_8,$ since we've used some of the colors of $C_4$ to color $C_7.$
I'm sure this works, if one specifies the procedure carefully. In coloring $G_7$ we should use all of $C_5$ first, so that we use as few colors from $C_4$ as possible. Then there will be enough colors remaining in $C_4$ to color $C_8$ without any fear of conflicts.
I leave it to you to fill in the details, and provide the proof. The proof will be trivial, I think, once the procedure is specified properly. I'm having trouble formalizing it at the moment.