7
$\begingroup$

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)?

  • 0
    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.2012-02-25

1 Answers 1

1

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.

  • 0
    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.2012-02-25