Proving that the complement of a bipartite graph has chromatic number equal to clique number - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-20T09:00:34Z http://mathoverflow.net/feeds/question/89459 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/89459/proving-that-the-complement-of-a-bipartite-graph-has-chromatic-number-equal-to-cl Proving that the complement of a bipartite graph has chromatic number equal to clique number David Galvin 2012-02-25T03:08:21Z 2012-02-25T03:43:37Z <p>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.</p> <p>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.</p> <p>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?</p> http://mathoverflow.net/questions/89459/proving-that-the-complement-of-a-bipartite-graph-has-chromatic-number-equal-to-cl/89463#89463 Answer by Russ Woodroofe for Proving that the complement of a bipartite graph has chromatic number equal to clique number Russ Woodroofe 2012-02-25T03:43:37Z 2012-02-25T03:43:37Z <p>According to Wikipedia<br> http://en.wikipedia.org/wiki/König's_theorem_(graph_theory)#Connections_with_perfect_graphs <br> the statement that $\chi(\overline{G}) = \omega(\overline{G})$ for all bipartite $G$ is actually equivalent to König's Theorem.</p>