Göm meny

TATA64 Course information



Lecturer and Examiner: Carl Johan Casselgren



Literature

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

J.A.Bondy and U.S.R.Murty, Graph Theory with Applications, North-Holland, 1976.

Both these books are available online (for personal use only).

Examination

Hand-in problems

Course Plan

There will be 13 lectures and 5 seminars where students' solutions to the hand-in exercises shall be presented.
A preliminary plan is the following.

Le 1-2: Basics. Eulerian circuits. Trees.
Bondy-Murty: 1.1-1.7, 2.1-2.4, 4.1
Diestel: 1.1-1.3 up to Prop 1.3.3, 1.5 up to Cor 1.5.4, 1.6-1.8, 1.10
Warm-up problems: 1.1-1.3, 1.6-1.8, 1.12, 1.13-1.15, 1.21, 1.23, 1.31-1.33, 1.39

Seminar 1.

Le 3-4: Matchings, Coverings and Independent sets
Bondy-Murty: 5.1-5.4, 7.1
Diestel: 2.1 (except part on stable matchings), 2.2 up to Thm 2.2.3
Warm-up problems: 2.3, 2.8

Seminar 2.

Le 5-7: Connectivity and Menger's theorem
Bondy-Murty: 3.1-3.2
Diestel: 1.4 up to Thm 1.4.3, 3.1, 3.3
Warm-up problems: 3.2, 3.6

Seminar 3.

Le 8-10: Graph Coloring. Planar Graphs. Turan's theorem
Bondy-Murty: 8.1-8.3, 8.5, 9.1-9.6, 7.3
Diestel: 5.1-5.2 (except the parts on coloring number and k-constructible graphs),
Thms 4.2.9, 4.2.10, 4.4.1, 4.4.2, 4.4.6 on planarity, 7.1 up to Thm 7.1.2, Hadwiger's conjecture in 7.3
Warm-up problems: 4.2, 4.3, 4.10, 4.11, 4.17a, 4.19, 4.20

Seminar 4.

Le 11-12: Edge Coloring. Hamilton cycles
Bondy-Murty: 6.1-6.2, 4.2 up to Thm 4.6
Diestel: 5.3, 10.1 up to Thm 10.1.3, 10.2 up to Cor 10.2.2
Warm-up problems: 5.1, 5.2, 5.9, 5.14

Le 13: Ramsey Theory
Bondy-Murty: 7.2
Diestel: 9.1 up to Thm 9.1.2, 9.2 up to Thm 9.2.2
Warm-up problems: 6.1

Seminar 5.



Sidansvarig: carl.johan.casselgren@liu.se
Senast uppdaterad: 2023-12-21