MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

## Proving that the complement of a bipartite graph has chromatic number equal to clique number

I'm teaching an undergraduate combinatorics class, using Harris et al.'s book Combinatorics and Graph Theory''. In Section 1.6 there is an exercise asking to show that for the complement of a bipartite graph, the chromatic number equals the clique number. I assigned the problem to my students, without thinking much about the solution.

Now that I've given it some thought, I've found what seems to be a very natural proof using Hall's marriage theorem, and have found other proofs online that use the K\"onig-Egerv\'ary theorem. Unfortunately, my students don't know either of these results ... they don't appear until Section 1.7 of the book.

My question is this: is there a way of showing (directly, i.e., not using Lov\'asz's perfect graph theorem) that $\chi(\overline{G})=\omega(\overline{G})$ for bipartite $G$, that avoids Hall's theorem or the K\"onig-Egerv\'ary theorem? In particular, is there a way that might be found by a student unfamilar with these results, who has only seen the basics of coloring (definition of $\chi$, greedy algorithm, Brooks' theorem, some basic bounds), and knows nothing yet about perfect graphs and the perfect graph theorem?

-
Hmm. It is easy to see that $\chi\left(\overline G\right) = n - \left(\text{number of edges in a maximum matching of }G\right)$ and $\omega\left(\overline G\right) = \left(\text{size of maximal independent subset of }G\right) = n - \left(\text{size of minimal vertex cover of }G\right)$ (because independent subsets are exactly the complements of vertex covers). So this exercise doesn't just follow from König's theorem; it is also equivalent to it... – darij grinberg Feb 25 2012 at 3:50
PS: By "equivalent", I mean "equivalent by an argument substantially simpler than any proof I know for König's theorem". – darij grinberg Feb 25 2012 at 3:51
Thanks, this is a very helpful response! – David Galvin Feb 25 2012 at 3:58

the statement that $\chi(\overline{G}) = \omega(\overline{G})$ for all bipartite $G$ is actually equivalent to König's Theorem.