Graph Theory (Winter Semester 2013/14)
- Lecturer: Prof. Dr. Maria Axenovich, Torsten Ueckerdt
- Classes: Lecture (0104500), Problem class (0104510)
- Weekly hours: 4+2
| Schedule | |||
|---|---|---|---|
| Lecture: | Monday 9:45-11:15 | 1C-03 | Begin: 21.10.2013 |
| Wednesday 8:00-9:30 | Neue HS Geb. 20.40 | ||
| Problem class: | Friday 11:30-13:00 | RPH HS Geb. 40.32 | Begin: 25.10.2013 |
| Lecturers | ||
|---|---|---|
| Lecturer | Prof. Dr. Maria Axenovich | |
| Office hours: Fr. 10:00-11:00 | ||
| Room 1.043 Kollegiengebäude Mathematik (20.30) | ||
| Email: maria.aksenovich@kit.edu | Problem classes | Torsten Ueckerdt |
| Office hours: | ||
| Room Kollegiengebäude Mathematik (20.30) | ||
| Email: torsten.ueckerdt@kit.edu | ||
Announcement
- The grades for Graph Theory are published on the 4th floor of Allianz building.
- The post-exam review takes place on April 28 from 1pm to 2pm in room 1C-01 of Allianz building.
- Oral reexaminations are possible on individual schedule. Please feel free to contact us.
In summer term 2014 we offer the seminar Topics in Graph Theory. Interested students should come to the kick-off meeting on Thursday, February 6.
For further information see Topics in Graph Theory.
Course description
The course will be concerned with topics in classical and modern graph theory:
- Properties of trees, cycles, matching, factors
- Forbidden subgraphs
- Planar graphs
- Graph colorings
- Random graphs
- Ramsey theory
- Graph minors
Objectives
The class is oriented towards problem solving. The goal of the course for
the students is to gain knowledge about the fundamental concepts in graph theory,
solve interesting problems, learn how to write and present the proofs creatively.
Prerequisites
basic knowledge of linear algebra; appropriate for students starting from 5th semester
Examination
Problem sheets
- There will be a problem sheet every Monday (starting on October 21) with 4 problems for 5 points each.
- The problems can be solved in small groups and solutions can be submitted separately or in groups of two or three.
- Every student works on three problems of his/her choice.
- Due date is Wednesday the following week at 12:00 am.
- The problems can be submitted during the lecture or deposited in a box in the 4th floor of Allianz building.
The problem sheets will be handed out in the Monday lecture.
Written exam
There will be a written exam at the end of semester on
February 26, 2014, 9:00am to 1:00pm
The exam takes place in HS Nusselt (building 10.23) und HS Tulla (building 11.40).
Registration
Begin: January 15, 2014
End: February 15, 2014
To register for the exam "Graph Theory" go to the student portal at https://studium.kit.edu. The registration is open from 15th of January 15 to 15th of February. Registerations later than February 15 can only be done in person at the secretary. Registrations can be canceled before February 26 via student portal and at February 26 on site in person.
Day of exam
Each student reads up his seat and should be 10 minutes before the exam begins at his/her seat.
Grading
The final grade for the course is calculated based on the points achieved in the written exam. If a student passes the written exam then his or her grade can be raised by one, two or three steps. This is done based on the points the student achieved in the homework as follows:
- At least 108 points on 9 problem sheets or at least 90 points on 7 problem sheets: grade 1 step better
- At least 115 points on 9 problem sheets or at least 95 points on 7 problem sheets: grade 2 steps better
- At least 122 points on 9 problem sheets or at least 100 points on 7 problem sheets: grade 3 steps (a full grade) better
References
The main source is the book Graph Theory by Reinhard Diestel. The English edition can be read for free on the author’s web site (http://diestel-graph-theory.com/).
Additional literature
- D. West -- Introduction to graph theory
- B. Bollobas -- Modern graph theory
- A. Bondy and U.S.R. Murty -- Graph Theory
- L. Lovasz -- Combinatorial problems and exercises
- G. Chartrand, L. Lesniak and P. Zhang -- Graphs & Digraphs
Lecture notes
There exist notes taken by a student during the winter term 2011/12. The current version is not approved and claims neither completeness nor correctness.
- unrevised notes up to Menger's theorem: (pdf)
Additionally, there are lecture notes containing all relevant definitions, notation and theorems from the lecture. However, they provide no proofs, no motivation and only a few examples.
- lecture notes: (pdf)