Upper bound for chromatic number of partitioned graph. Let $G=(V,E)$ be a graph that satisfies:
$(1)$ $V= \dot\cup_{k=1}^n V_k.$
$(2)$ For all $i,j \in \{1,...,n\}$ there exists a vertex in $V_i$ and a vertex in $V_j$ that are not an edge of $G$.
Then it holds that $\chi(G) \leq v-n+1,$ where $v$ denotes the number of vertices of $G$.
My idea was to use induction on $n$, where the base case $n=1$ follows since $\chi(G)$ has to be less or equal than $v$.
Now for the induction step, I can consider the parition $V=(\dot\cup_{k=1}^n V_k) \dot\cup V_{n+1}.$ Using the induction hypothesis yields $\chi(G') \leq v(G') - n+1$ and $\chi(G'') \leq v(G''),$ where $G'$ denotes the induced Graph on $V_1,...,V_k$ and $G''$ denotes the Graph induced by $V_{n+1}$. However, I am neither sure how to combine the two colorings to obtain the desired statement nor if this is a good approach. Thanks in advance for any help.
 A: My previous answer was too brief and raised many questions. I have tried this time to lay out the evidence in as much detail as possible.
Let $G=(V,E)$ be a graph that satisfies:
(1)
$$
V=\bigsqcup_{k=1}^n V_k
$$
(2)
For all $i,j\in\{1,\ldots,n\}$ there exist $x_i\in V_i$ and $x_j\in V_j$ that $x_ix_j\notin E$.
Then $\chi(G)\leq v-n+1$, where $v=|V|$.
Proof.
Let us first introduce the concept of multiplicity of colors.
Let the vertices of some graph are colored in several colors and $c$ is one of the colors. Let color $c$ have $k$ vertices. Then the multiplicity of color $c$ is the number $\nu(c)=k-1$.
Let $v_i$ be the number of vertices in $V_i$.
By induction on $n$ we prove that there exists a proper coloring of vertices of graph $G$ such that:
(i) the total number of distinct colors is at most $v-n+1$;
(ii) vertices of the same color lie in different sets $V_i$;
(iii) the sum of multiplicities of all colors is at most $n-1$.
Let us color the vertices of $V_1$ with $v_1$ of colors.
Note now that for proper coloring $V_2$, we additionally need only $v_2-1$ of different colors. Let us paint the vertex $y$ of $V_2$ that is not adjacent to the vertex $x$ of $V_1$ with the same color as $x$.
Thus it is easy to see that our statement is true for $n=1,2$.
Suppose we have already made $s\geq2$ steps and colored vertices of the set $W=V_1\cup\ldots\cup V_s$ such that all conditions (i)-(iii) with $n=s$ are satisfied. Let $C$ be the set of all those colors that if $c\in C$ then $\nu(c)>0$. By condition (iii) we have $\nu(C)=\sum_{c\in C}\nu(c)\leq s-1$.
Let's take the next step.
Let us choose vertices $y_1,\ldots,y_s$ in the set $V_{s+1}$ and in each set $V_i$ one vertex $x_i$ such that $x_i$ is not adjacent to $y_i$.
If vertex $x_i$ has color $c$ and $c\notin C$ then let us color vertex $y_i$ into color $c$, and let us color other $v_{s+1}-1$ vertices of set $V_{s+1}$ into new $v_{s+1}-1$ colors. Put $C'=C\cup\{c\}$.
Clearly, the resulting proper coloring satisfies all conditions (i)-(iii).
Thus we can assume that $X=\{x_1,\ldots,x_s\}$ are colored by colors from $C$.
If for each color $c\in C$ the number of vertices from $X$ of color $c$  is not greater than $\nu(c)$, then $s\leq\sum_{c\in C}\nu(c)\leq s-1$, which is impossible.
Hence, there exists a color $c\in C$, for which there are $\nu(c)+1$ vertices in the set $X$, that is, all vertices of color $c$ lie in $X$.
In order not to introduce new notations, we assume that all vertices of $X$ have color $c$. Let first the elements of the set $Y=\{y_1,\ldots,y_s\}$ be pairwise distinct.
Now we color the set of vertices $Y$ and re-color the vertices of the set $X$ so that the proper coloring is obtained:
we color the vertices $Y$ with $s-1$ of new colors and the color $c$,
and $x_i$ is painted exactly like $y_i$.
If $V_{s+1}$ has vertices distinct from $y_i$, we use new colors for them. So we don't need more than $v_{s+1}-1$ of new colors to do this step.
It is easy to see that this coloring satisfies conditions (i)-(iii).
If there are the same elements $y_i$ among them, all reasoning holds, but we just need fewer new colors.
A: I think I finally understand @kabenyuk's answer. I'm going to rewrite it in a way that I find easier to understand. To justify such a repetitive answer, I will state the result in a slightly more general form.
Theorem. Let $n$ be a positive integer. Let $G=(V,E)$ be a (finite) graph of order $v=|V|$. Suppose the vertex set $V$ is partitioned into $n$ disjoint subsets $V_1,\dots,V_n$. Let $W_i=V_1\cup V_2\cup\cdots\cup V_i$. Suppose that, for each $j$ ($1\lt j\le n$), there exist a set $X_j\subseteq W_{j-1}$ and a mapping $f_j:X_j\to V_j$ such that $|X_j|=j-1$ and $\{x,f_j(x)\}\notin E$ for all $x\in X_j$. Then $\chi(G)\le v-n+1$.
[This is more general because the set $X_j$ is not required to consist of one element from each of the sets $V_1,\dots,V_{j-1}$, just any $j-1$ elements of $W_{j-1}=V_1\cup\cdots\cup V_{j-1}$.]
The proof is by induction on $n$. The case $n=1$ being trivial, we assume $n\gt1$. By induction, the subgraph induced by $W_{n-1}$ can be properly colored with at most $|W_{n-1}|-n+2$ colors; let such a coloring be fixed.
By hypothesis we have a set $X_n\subseteq W_{n-1}$ and a mapping $f_n:X_n\to V_n$ such that $|X_n|=n-1$ and $\{x,f_n(x)\}\notin E$ for all $x\in X_n$. We consider two cases.
Case 1. Every color occurring in $X_n$ also occurs in $W_{n-1}\setminus X_n$.
Suppose $k$ different colors $c_1,\dots,c_k$ occur in $X_n$. Choose vertices $v_1,\dots,v_k\in W_{n-1}\setminus X_n$ with $v_i$ of color $c_i$. Then $\{v_1,\dots,v_k\}\cup X_n$ is a set of $k+n-1$ vertices of $G$ which is properly colored with $k$ colors, whence $\chi(G)\le v-n+1$ by giving distinct colors to all other vertices of $G$.
Case 2. Some color $c$ occurs in $X_n$ but not in $W_{n-1}\setminus X_n$.
By assigning a distinct new color to each vertex in $V_n$ we get a proper coloring of $G$ with at most $v-n+2$ colors. But since color $c$ occurs only in $X_n$, we can abolish color $c$ by recoloring each vertex $x$ of color $c$ with the color of the vertex $f_n(x)$, thus obtaining a proper coloring of $G$ with at most $v-n+1$ colors.
