Timeline for Proving that the complement of a bipartite graph has chromatic number equal to clique number
Current License: CC BY-SA 3.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 11, 2015 at 7:39 | answer | added | Ali | timeline score: 0 | |
| Feb 25, 2012 at 3:56 | vote | accept | David Galvin | ||
| Feb 25, 2012 at 3:51 | comment | added | darij grinberg | PS: By "equivalent", I mean "equivalent by an argument substantially simpler than any proof I know for König's theorem". | |
| Feb 25, 2012 at 3:50 | comment | added | darij grinberg | 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... | |
| Feb 25, 2012 at 3:43 | answer | added | Russ Woodroofe | timeline score: 3 | |
| Feb 25, 2012 at 3:08 | history | asked | David Galvin | CC BY-SA 3.0 |