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?
