Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

In Section 1.6 of Harris et al.'s book Combinatorics and Graph Theory, there is a question asking to show that the chromatic number equals the clique number for the complement of a bipartite graph. 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. Unfortunately, my students don't know this result ... it doesn't appear until Section 1.7 of the book!

My question is this: is there a way of showing $\chi(\overline{G})=\omega(\overline{G})$ for bipartite $G$, that avoids Hall's theorem? In particular is there a way that might be found by a student unfamilar with Hall, who has only seen the basics of coloring (definition of $\chi$, greedy algorithm, Brooks' theorem, some basic bounds)?

share|cite|improve this question
After some searching online I have found another proof, using the K\"onig-Egerv\'ary theorem; but this is also unsatisfactory since that result also appears in Section 1.7 of the book. – David Galvin Feb 25 '12 at 3:11

A first principles proof appears on page 129 of Diestel's Graph Theory. It is a bit lengthy, so I will not reproduce it here. Also, it is the original proof and Lovász and is quite clever. I would not expect your students to come up with this on their own.

Edit: I just noticed you want the result only for complements of bipartite graphs. The proof I reference is for general graphs. Perhaps it simplifies greatly if you make the additional assumption.

share|cite|improve this answer
Thanks for the reference to Diestel; as you say, though, these are arguments that one would not expect a student to discover, and so don't seem to be what Harris et al. were thinking of when writing the exercise. – David Galvin Feb 25 '12 at 5:11

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.