Timeline for Interesting and accessible topics in graph theory
Current License: CC BY-SA 3.0
2 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 11, 2011 at 4:29 | comment | added | David Eppstein | If you're covering matching theory, I would add König's theorem (in a bipartite graph max matching + max independent set = #vertices), the theorem that a regular bipartite graph has a perfect matching, and Petersen's theorem that a bridgeless cubic graph has a perfect matching (e.g. a triangulated 2-manifold has a matching of its triangles). But I have to admit that last week in the matching part of my graph algorithms class I covered only König and Gale–Shapley because it's about graph algorithms not graph theory and I needed the remaining lecture time to cover the Hopcroft–Karp algorithm. | |
| May 10, 2011 at 9:47 | history | answered | darij grinberg | CC BY-SA 3.0 |