The compartment for graph. Suppose that $G$ is a graph, which is not a clique. Prove that there is a
division of the set of vertices $V(G)$ into two subsets $V_1$ and $V_2$ such that
$\chi(G)< \chi(G [V1]) + \chi (G [V2])$
where $G[V_i]$ is a subgraph induced by the set $V_i$
I'm asking for any advice. I tried do it, but without any success.
 A: Note that $\chi(G)\leq\chi(G[V_1])+\chi(G[V_2])$ for every partitioning.
Let $\chi(G)=n$.
Let $V_1$ be the vertex set of a maximal clique (of size $k$) in $G$ and $V_2$ all other vertices.
Since $G$ is not complete $V_2$ is not empty.
Obviously $k\leq n$. If $k=n$ we found our partition, so we may assume $k<n$.
Let $G_1=G[V_1]$ and $G_2=G[V_2]$ and suppose
$\chi(G)=\chi(G_1)+\chi(G_2)$, which implies $\chi(G_2)=n-k$.
Now make a coloring of $G$ by taking any $n-k$-coloring for $G_2$
and use $k$ new colors for the vertices of $G_1$.
This is an $n$-coloring of $G$, so it cannot be reduced.
Specifically this means that there is a vertex $v_1$ that has color 1 and
whose neighbours use all other colors, so we find that $v_1$ is adjacent to all of $G_1$,
contradicting our assumption that $G_1$ is a maximal clique.
A: Take a vertex $v$ that is not adjacent to every other vertex (Clearly if one does not exist the graph is complete). Let $V_1$ be $v$ and all of its neighbors. Take a minimal coloring of $V_1$ and $V_2$ so both parts use different colors. This gives a coloring of $G$ with $G[V_1]+G[V_2]$ vertices. Since $v$ is the only vertex with that color and $v$ is not adjacent to any vertex in $V_2$ we can swap the color of $v$ with a color of $V_2$. Obtaining a coloring of $G[V_1]+G[V_2]-1$ colors.
