max planck institut
informatik
informatik
| Lectures: | Tuesday 14-16 (R.024 E1.4) / Thursday 14-16 (R.024 E1.4) |
|---|---|
| Lecturers: | Artur Jez and Jens M. Schmidt |
| Tutorials: | Wednesday 16-18 (R.023) and Friday 14-16 (R.022) |
| Tutors: | Andreas Schmid, Harry Zisopoulos |
This is a first course in graph theory dedicated to both, computer science and mathematics students. Topics include basic notions like graphs, subgraphs, trees, cycles and further concepts like connectivity, packing, colorings, matchings, planarity, perfect graphs, random graphs, minors etc..
| Prerequisites: | Basics in discrete mathematics, probability theory and calculus. |
|---|---|
| Literature: | Most of the lecture, but not all, will follow Reinhard Diestel's book on graph theory. There is a free PDF-version on this page. |
| Credit: | SWS: 4+2, Credit Points: 9 |
| Exam: | There will be an oral or written exam at the end of the semester, depending on the number of students. Your grade will only be dependent on the exam. |
| Date | Topic | Lecturer | Exercises |
|---|---|---|---|
| Apr 16 | Basic techniques, graphs, degrees, cycles, Handshake lemma, k-(edge-)connectivity | Jens | Exercise 1 |
| Apr 18 | Trees, bipartite graphs, Eulerian graphs, subdivisions and minors | Jens | |
| Apr 23 | Matchings, König's theorem, Hall's theorem, stable matchings | Artur | Exercise 2 |
| Apr 25 | Tutte's perfect matching theorem, connection to determinants | Artur | |
| Apr 30 | Nash-Williams' tree-packing theorem | Jens | Exercise 3 |
| May 2 | 2-connectivity, blocks, BC-tree, Menger's theorem and variants | Jens | |
| May 7 | Linkages | Jens | Exercise 4 |
| May 9 | No lecture (Ascension Day) | ||
| May 14 | Flows, Ford-Fulkerson theorem (Room Change: R.023) | Artur | Exercise 5 |
| May 16 | Circulations, nowhere-zero-flows and Tutte's conjectures | Artur | |
| May 21 | Graph coloring, chromatic
number, greedy algorithm, Brook's theorem | Artur | Exercise 6 |
| May 23 | Chromatic index, Coloring bipartite graphs, Vizing's theorem | Artur | |
| May 28 | Chordal graphs, perfect graphs, perfect graph theorem (weak version) | Artur | Exercise 7 |
| May 30 | No lecture (Corpus Christi) | ||
| June 4 | List colorings, edge-list coloring conjecture, Galvin's theorem | Jens | Exercise 8 |
| June 6 | Planar graphs, embeddings+duality, 5-color theorem, discharging method and 4-color theorem | Jens | |
| June 11 | Euler's formula, high genus surfaces, graph genus, Kuratowski's criterion, crossing number | Artur | Exercise 9 |
| June 13 | Extremal graphs: Hadwiger's conjecture, Heawood bound for high genus graphs | Artur | |
| June 18 | cancelled | tutorials take place! | |
| June 20 | cancelled | ||
| June 25 | WQO and consequences, graph minor theorem, hereditary property | Artur | Exercise 10 |
| June 27 | Kruskal's tree theorem, tree decompositions | Artur | |
| July 2 | Conditions for small treewidth, partial k-trees, brambles, tree-width duality | Jens | Exercise 11 |
| July 4 | Cops and robber games, infinite graphs, König's lemma | Artur | |
| July 9 | Hamiltonian cycles, sufficient conditions | Jens | Exercise 12 |
| July 11 | Necessary conditions, Grinberg's theorem, Chvatal's theorem, Barnette's conjecture | Jens | Barnette's Conjecture Slides |
| July 16 | Platonic Solids, edge- and cycle space, cycle bases, Tutte's theorem on non-separating induced cycles bases | Jens | Exercise 13 |
| July 18 | Maximum adjacency orderings, sparse k-edge-connected subgraphs, pendant pairs, Stör-Wagner | Jens | |
| July 23 | Ramsey theorem and generalizations, random graphs, probabilistic method | Artur | |
| August 2+5 | 13:00-18:00: Exams | Artur+Jens | |
| October 7-9 | Re-exams (by appointment) | Artur+Jens |