Upper bound for chromatic number of partitioned graph.

Solution 1:

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.

Solution 2:

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.