Bipartite Graph with fixed degree sequence Coloring Problem A simple bipartite graph G has 20 vertices, of which 18 have degree 7, the others have degree 6. Find the chromatic number of the complement of G. 
I think that the two vertices with degree 6 must be in different color class and I guess the chromatic number is 10 but I haven't figure out a proof yet. 
 A: For $i=6,7$ let $a_i$ [$b_i$] be a number of vertices of the graph $G$ belonging to a color class $A$ [$B$] with degree $i$. Then we have the following system.
$\cases{a_7+b_7=18\\
a_6+b_6=2\\ 
6a_6+7a_7=6b_6+7b_7}$
Since $a_6+b_6=2$ and $b_6-a_6$ is divisible by $7$, $a_6=b_6=1$. Then $a_7=b_7=9$. Therefore each color class of the graph $G$ has $10$ vertices. 
Since complement $G^c$ of the graph $G$ consists of two cliques on each of color classes, $\chi(G^c)\ge 10$. 
To show an upper bound for $\chi(G^c)$ we present the coloring of its vertices into $10$ colors constructed as follows. First we claim that the graph $G$ has a perfect mathching $M$. In order to show that we shall check that $G$ satisfies the conditions of Hall’s Marriage Theorem. Let $W$ be any non-empty subset of the set $A$. If $|W|\le 6$ then $|W|\le 6\le|N_G(v)|\le |N_G(W)|$ for any vertex $v\in W$. If 
$|W|\ge 5$ then $N_G(W)=B$, because any vertex $u\in B$ has degree at least $6$, so it is adjacent to some vertex in $W$. Now the coloring which puts to each pair of matched by $M$ vertices different color is the required. 
