I'm asked to prove the following:
Show that for any undirected non-complete graph $G$ there is a partition $V(G)=V_1\sqcup V_2$ such that $\chi(G[V_1])+\chi(G[V_2])>\chi(G)$
I managed to show that we can assume that every vertex $x$ with non-full degree has degree atleast $\chi(G)-1$ (otherwise, we may take $V_1=\{x\}$ and consider its neighbors), but then I get stuck. I also considered doing induction by taking the "almost-complete" non-complete graph (i.e. a complete graph with one edge removed) and removing edges, but I'm not sure what to do in the induction step. Any help would be appreciated.
Best Answer
Let $v$ be a vertex with non-full degree. Take $V_1 = \{v\} \cup N(v)$ and $V_2 = V(G) \setminus V_1$. Now notice that if we can color $V_1$ with $k_1$ colors and $V_2$ with $k_2$ colors then we can color $G$ with $k_1+k_2-1$ colors by coloring $v$ with one of the colors of $V_2$ (this comes from the fact that $v$ cannot have the same color with any of the other vertices in $V_1$). This gives us that $\chi(G) \leq \chi(G[V_1]) + \chi(G[V_2]) - 1$ and we are done.