Bounding chromatic number for a specific graph A school has $n$ students and $k$ disjoint classes. Every two students in the same class are friends. For each two different classes, there are two people from these classes that are not friends. Prove that we can divide students into $n-k+1$ groups so that students in same group are not friends.
As far as i know the problem belong to Lovasz but searching for it under his name proved futile.
Any reference or solution would be greatly appreciated.
 A: I think i can prove it, now. And the previous prove is wrong.....

Ok, although this example is wrong, but it may help understand the problem.

wrong example:
There are five classes, 1,2,3,4,5. Five students a,b,c,d,e.
And the specific distribution is:
Class 1: a,b. Class 2:b,c. Class:3:c,d. Class 4:d,e. Class 5:e,a.
I think it satisfies ur condition.But we can't get them in a group.

proof.
We can use math induction to solve this. We do induction on $n$.
When $n=1$, it's easy to prove.
We assume when  $\le n-1$, are true.
We consider $n$.

(1) If no class has more than one student, it's obviously we can get all students in a group.

(2) If a class K has more than one students, we assume it has $m$ students.
Then we divide the graph into $m$ subgraph.
The $i$th graph contains the $i$th student in class K and all other classes which have a student who is not friend of the $i$th student.
Obviously two subgraph may have the same original class, but we can simple remove the original from one subgraph.
We assume the $i$th subgraph has $n_i$ students and $k_i$ class. And we have 
$$\sum_{i=1}^m n_i=n\\
\sum_{i=1}^{m}k_i=k-m+1$$
The second equation has $(m-1)$, because class K are count for $m$ times. 
Because K has more than one students, $n_i\le n-1$. By induction we can divide those subgraphs into no-friend groups. 
$$\sum_{i=1}^m (n_i-k_i+1)=n-k+1$$
Therefore, we have $n-k+1$ no-friend groups.

Then we finish the induction. And prove it. (I hope nothing is wrong....)
A: Clearly we can put the $n$ objects into $n$ distinct groups such that there are no friends in a group. If we can merge at least $k-1$ of these students into existing group(s), then we are done. So let's do it! Note that students from the same class clearly cannot be in the same group.
We are told that between any two classes, there are two students who are not friends. So, for each class, try placing one student into some existing group of student(s) from other class(es). If we can do this at least $k-1$ times then we are done.
So suppose not. I.e. suppose there is some class $j$ for which we cannot move any student into an existing group. Denote by $v_i$ the student in class $i$ who is not friends with some student $v_j$ in class $j$ where $i\neq j$ and $1\leq i\leq k$. Since no student in class $j$ can be grouped with any of these students $v_i$ (otherwise we would not have a problem), this must mean that each student $v_i$ is already in a group with some other student(s) and that this "other student(s)" is friends with $v_j$. For each groups containing students $v_i$, either 


*

*There is some group containing only students among the $v_i$. For each such group, we can split the group and pair each $v_i$ with the student $v_i$ is not friends with from class $j$, or else 

*All ($k-1$) groups contain some student that is not among the $v_i$
In either case, we end up with at least $k-1$ distinct "merges" and so we are done.
