6FMA10 Graph Theory

Course information

Lecturer and Examiner: Carl Johan Casselgren

Literature

R. Diestel, Graph Theory, Springer, 3rd or later edition.

The book is available online (for personal use only).

Some notation for the course.

Examination

Hand-in assignments and oral presentation.

Course Plan

There will be (approximately) 12 lectures and a set of exercises for each lecture.
A preliminary plan for 2020 is the following.

Le 1-2: Basics. Eulerian circuits. Trees.
Diestel: 1.1-1.8, 1.10

Homework 1.

Homework 2.

Le 3-4: Matchings and Factors
Diestel: 2.1-2.2

Homework 3.

Homework 4.

Le 5: Connectivity
Diestel: 1.4, 3.1-3.3

Homework 5.

Le 6-7: Coloring vertices. Planar graphs.
Diestel: 5.1-5.2, 4.4 (skim trough 4.1-4.2 for general definitions of planar graphs)

Homework 6.

Homework 7.

Le 8-9: Edge Coloring. Perfect graphs. List coloring
Diestel: 5.3-5.5

Homework 8.

Homework 9.

Le 10-12: Extremal graph theory. Random graphs
Diestel: 7.1-7.5, 11.1-11.4

Homework 10.

Homework 11.

Homework 12.

Sidansvarig: carl.johan.casselgren@liu.se
Senast uppdaterad: 2020-05-07