# chromatic number and subgraph

Prove that any graph $G$ with $n$ vertices and $\chi(G)=k$ has a subgraph $H$ such that $H \simeq \overline{K_p}$ where $p=n/k$ and $K_p$ is the complete graph with $n/k$ vertices.

My attempt: Because $\chi(G)=k$ it must be $G \subseteq K_{p_1 p_2 \cdots p_k}$ where $\displaystyle{\sum_{j=1}^{k} p_j =n}$.

Can I consider now that $p_j =n/k$ for all j?

If no then the other cases is to have $p_j >n/k$ for some $j \in \{1, \cdots ,k\}$.

But now how can I continue?

-
Someone?? I really need this. –  passenger Feb 3 '12 at 22:21
You just asked an hour ago. You can't be upset that there's no answer yet. –  Graphth Feb 3 '12 at 22:37
@Graphth: I am not upset. Sorry for being so hurry. –  passenger Feb 3 '12 at 22:46
I don't understand the question. There is no reason to believe that $n/k$ is an integer. If it isn't, then what is meant by a graph with a fractional number of vertices? Also, what is meant by that bar over the $K_p$? I thought it might mean complement, but complement with respect to what? –  Gerry Myerson Feb 3 '12 at 23:25
The color classes are independent sets of average size n/k. –  Louis Feb 3 '12 at 23:40

If $\chi(G) = k$, it means we can color the graph with $k$ colors, $c_1, \ldots, c_k$. Each color class, $c_i$, consists of some vertices $V_i$. Necessarily, the vertices in $V_i$ are independent, or we could not color them all the same color, $c_i$.
Now, assume that every color class contains less than $n / k$ vertices. Then the total number of vertices in the graph is $|G| < k \cdot (n/k) = n$. This isn't possible since we assume $|G| = n$. Therefore, some color class contains at least $n / k$ vertices. Since the vertices in a color class are independent, we have an independent set of size at least $n / k$.
So, OP wants the complement of $H$ to be $K_p$, not, as written, $H$ to be the complement of $K_p$. I think you have successfully decoded the question! –  Gerry Myerson Feb 4 '12 at 5:05