| [Announcements] | [General Information] | [Additional Material] | [Schedule] | [TD] |
The topic of this course is Graph Theory. Graphs are mathematical objects that can model complex networks with varying applications. In this course we take an approach that focuses on the mathematical side of things: we want to understand and formally prove interesting properties exhibited by graphs. We will do this from a computer scientist's perspective, often pausing to ponder the algorithmic and complexity-theoretic properties of the objects we study.
More information on the topics to be covered appears in the schedule below (which will be updated during the semester).
The course consists of 1.5 hours of weekly lectures, followed by 1.5 hours of TD (exercise sessions).
Grading: Your final grade is the result of the formula 0.7E+0.3CC, where E is your grade in the final exam and CC is your grade in a midterm exam that will be organized at some point in the middle of the semester.
Here you will find a tentative schedule (updated regularly throughout the semester) and the slides we will use in class.
| Lecture No. | Date | Topic | Notes |
|---|---|---|---|
| 1 | 12/9 | Introduction | |
| 2 | 19/9 | Trees | |
| 3 | 26/9 | Bipartite Graphs | |
| 4 | 3/10 | Bipartite Graphs Continued | |
| 5 | 10/10 | Menger's Theorem | |
| 6 | 17/10 | Coloring | |
| 7 | 24/10 | More Coloring | |
| 8 | 31/10 | Midterm Exam (tentative) | |
| 9 | 7/11 | Planar Graphs | |
| 10 | 14/11 | Chordal Graphs | |
| 11 | 21/11 | Split and Interval graphs | |
| 12 | 28/11 | Cographs and Perfect graphs |
| TD No. | Exercises | Solutions |
|---|