6
$\begingroup$

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?

$\endgroup$
2
  • 4
    $\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$ Commented Feb 25, 2012 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$ Commented Feb 25, 2012 at 3:51

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
0
0
$\begingroup$

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$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .