Home | deutsch | Impressum | Sitemap | Intranet | KIT
Research Group on Discrete Mathematics

Secretariat
Kollegiengebäude Mathematik (20.30)
Room 1.044

Address
Institut für Algebra und Geometrie
Englerstr. 2
D-76131 Karlsruhe

Office hours:
Tu, Th, F 8:30-12:00

Tel.: +49 721 608 47412

Fax.: +49 721 608 46968

Graph Theory (Winter Semester 2017/18)

Lecturer: Prof. Maria Axenovich Ph.D., Mónika Csikós
Classes: Lecture (0104500), Problem class (0104510)
Weekly hours: 4+2


Review session

This is a Q&A session that takes place on 23. February, 14:00 - 18:00. Room: 1.039 (Building 20.30).
In order to make these hours more efficient, please send your questions by e-mail to Monika Csikos until Thursday noon.

Exam information

Date: February 27, 2018
Place: Johann-Gottfried-Tulla Hörsaal and Gaede-Hörsaal
Time: 08:00 -- 12:00

Registration deadline: 20 February

You can cancel your registration until 26 February.


Schedule
Lecture: Monday 14:00-15:30 SR 1.067
Wednesday 9:45-11:15 SR 1.067
Problem class: Thursday 9:45-11:15 Chemie-Hörsaal Nr. 2 (HS2)
Lecturers
Lecturer Prof. Maria Axenovich Ph.D.
Office hours: by appointment
Room 1.043 Kollegiengebäude Mathematik (20.30)
Email: maria.aksenovich@kit.edu
Problem classes Mónika Csikós
Office hours: Thursdays 11:30-12:30 (and upon request)
Room 1.039 Kollegiengebäude Mathematik (20.30)
Email: monika.csikos@kit.edu

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

Please register for the homework on this website.

A problem sheet will be published here every Wednesday (starting on October 18) with 4 problems for 5 points each. Due date is Wednesday the following week at 9:45 am.



Rules of submission:

  • In each paper that you submit, you shall leave a right margin of width at least 1/3 of the paper so that the tutors have enough space to write their comments.
  • The submitted pages must be stapled together and your name has to be written on the front page with capital letters.
  • The problems are solved and solutions are submitted by individual students or pairs of students.
  • Every submission shall contain the solution to at most three problems.
  • When submitting in pairs, each student shall write at least one solution.
  • You can write your solutions either in English (preferable) or in German.
  • You shall submit your solutions in a blue box labeled "Graph Theory" in the atrium of the math building (20.30).

Bonus

There is the possibility to obtain a bonus by successfully working the exercise sheets.

In order to receive the bonus you need to obtain at least half of the total amount of points on the first 6 sheets, as well as on the second 6 sheets.

The bonus will improve the grade of a passed exam of this lecture at the end of the semester by one step (0.3 or 0.4).

Written exam

There will be a written exam at the end of semester on

Date: February 27, 2018
Place: Johann-Gottfried-Tulla Hörsaal and Gaede-Hörsaal
Time: 08:00 -- 12:00


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. Bollobás -- Modern graph theory
  • A. Bondy and U.S.R. Murty -- Graph Theory
  • L. Lovász -- Combinatorial problems and exercises
  • G. Chartrand, L. Lesniak and P. Zhang -- Graphs & Digraphs

Lecture notes

There are lecture notes containing all relevant definitions, notation and theorems from the lecture. The first part includes only formulations and definitions. The second part includes the proofs.

  • lecture notes: ( pdf | last updated on 21 February )