Graph Theory
Dozent
Henning Bruhn-Fujimoto, Jens Maßberg, Dirk Meierling
Übungsleiter
Time
Monday 12-14 in H12
Thursday 14-16 in H12
Tuesday 14-16 in H12 exercise
Exam
There will be a written exam at the end of the lecture time as well as at the beginning of the summer semester. Getting 50% of the points of the exercise sheets is a prerequisite for the admission to the exam.
General comments
The lecture 'Graph Theory' is one of the basic lectures at our institute. It is necessary for the lecture 'Graph Theory 2' and helps to understand the contents of the lectures 'Optimization I', 'Optimization II', 'Probabilistische Methoden' as well as the whole area of discrete mathematics.
Many problems in graph theory are easily explained to non-experts - even to non-mathematicians. For example, consider the problem of coloring a map where every country receives one color but two countries with a common border receive distinct colors. How many colors do we need at most? It took almost 100 years until Appel and Haken solved this problem by proving that four colors always suffice. Their proof is extremely long and sophisticated. Nevertheless, as one highlight of the lecture we will prove a weakening of the 4-color-theorem, namely that five colors suffices.
Knowing the basic concepts of graph theory allows to describe many real world problems. In addition, there are many good possible topics in graph theory for bachelor and master theses.
Literature
R. Diestel, Graphentheorie, 4te Auflage, Springer 2010.
B. Bollobas, Modern Graph Theory, Springer 1998.
J.A. Bondy und U.S.R. Murty, Graph Theory, Springer 2008.
J.A. Bondy und U.S.R. Murty, Graph Theory with Applications, 1976.
D.B. West, Introduction to Graph Theory, Prentice-Hall 2005.
L. Volkmann, Graphen an allen Ecken und Kanten, 2011.