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?

  • 3
    $\begingroup$ 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... $\endgroup$ – darij grinberg Feb 25 '12 at 3:50
  • $\begingroup$ PS: By "equivalent", I mean "equivalent by an argument substantially simpler than any proof I know for König's theorem". $\endgroup$ – darij grinberg Feb 25 '12 at 3:51

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


Let $X$ and $Y$ be the partite sets of our bipartite, and let $H$ be a clique-subgraph of $\overline{G}$. Suppose that $X_H\subseteq X$ and $Y_H\subseteq Y$ be the sets of vertices occurring in $H$, thus, $|V(H)|=|X_H\cup Y_H|=\omega(\overline{G})$. Consider, as lists, the sets $L_X=X-X_H=\{v_0,\ldots,v_k\}$, and $L_Y=Y-Y_H$. Clearly, any coloring of $H$ should consume $\omega(\overline{G})$ colors. Consider such coloring of $H$. We show, however, that the list $L_X$ can be colored using only the colors assigned to $Y_H$, and, similarly, the list $L_Y$ can be colored with only those colors of $X_H$.

Each vertex in $L_X$ is non-adjacent, in $\overline{G}$, to at least one vertex in $Y_H$ (why?!). So we may proceed, in the list order, assigning to each vertex $v_i$ the color of one of its `non-adjacencies' in $Y_H$. This process should be successful at least for $v_0$, and we show that, in fact, the process shall prevail.

Suppose that $v_t\in L_X$ is the first vertex for which the assignment process is doomed. This means, exactly, that if $S_0\subseteq Y_H$ is the set of all non-adjacencies of $v_t$, then the colors of $S_0$ have been already consumed while coloring the vertices $v_0,\ldots,v_{t-1}$. Before pursuing the end :)) , we must declare some notation.\ \textbf{Notation:} For a subset $A\subseteq Y_H$, derive the set $D(A)\subseteq L_X$ of those vertices before $v_t$ colored by the colors of $A$. Clearly, $|A|=|D(A)|$. For a vertex $v$, let $c(v)$ denote, interchangeably, the 'current' color of $v$, or a certain other vertex with the same color.\

We run a procedure of three scenarios:

Set $i=0$ and $M= S_0\cup\cdots\cup S_i\subseteq Y_H$.

(1) If every vertex in $D(M)$ is adjacent to all vertices in $Y_H-M$, then the subgraph, of $\overline{G}$, induced on $(X_H\cup D(M)\cup\{v_t\})\cup(Y_H-M)$ is a complete subgraph of $\overline{G}$ whose order is $\omega(\overline{G})+1$, contradiction.

(2) If a vertex $w_i\in D(S_i)$ is non-adjacent, in $\overline{G}$ of course, to a vertex in $Y_H$, whose color (\textbf{VIOLET}) is not yet used, then we can re-color $w_i$ in violet, and since $c(w_i)\in S_i$, $c(w_i)$ is non-adjacent to some vertex $w_{i-1}\in D(S_{i-1})$. Then $w_{i-1}$ can abandon the color $c(w_{i-1})$ and get colored in the color $c(w_i)$. Proceeding this shift of colors, we reach a vertex $w_0\in S_0$ to which we assign the color of $c(w_1)$, after abandoning the color $c(w_0)$. Finally giving $v_t$ the color of $c(w_0)$. Thus, we overcome the situation, and proceed coloring the rest of the list $L_X$.

(3) If none of the above, let $S_{i+1}\subseteq Y_H$ consist of all vertices, out of $S_0\cup\cdots\cup S_i$, that are non-adjacent to any of the vertices in $D(M)$. Increase $i$ by one and back to 1.

This algorithm should always terminate with coloring the trouble vertex $v_t$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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