Sign up ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|cite|improve this question
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 '12 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 '12 at 3:51
Thanks, this is a very helpful response! – David Galvin Feb 25 '12 at 3:58

1 Answer 1

up vote 1 down vote accepted

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

share|cite|improve this answer
Thanks, Russ; this is most helpful! – David Galvin Feb 25 '12 at 3:58

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.