Graph Theory

Code	Completion	Credits	Range	Language
01TG	ZK	5	4P+0C	Czech

Relations:

Course guarantor:

Petr Ambrož

Lecturer:

Petr Ambrož, Jan Volec

Tutor:

Supervisor:

Department of Mathematics

Synopsis:

1. Basic notion of graph theory.

2. Edge and vertex connectivity (Menger Theorem).

3. Bipartite graphs.

4. Trees and forests.

5. Spanning trees (Matrix-Tree Theorem).

6. Euler tours and Hamilton cycles.

7. Maximal and perfect matching.

8. Edge coloring.

9. Flows in networks.

10. Vertex coloring.

11. Plannar graphs (Kuratowski theorem), vertex coloring of planar graphs.

12. Spectrum of the adjacency matrix.

13. Extremal graph theory.

Requirements:

Syllabus of lectures:

Syllabus of tutorials:

Study Objective:

Study materials:

Course textbooks:

[1] A. Bondy, U.S.R. Murty: Graph Theory, Springer-Verlag London, 2008.

[2] R. Diestel: Graph Theory (5th ed.), Springer-Verlag Berlin Heidelberg, 2017.

Additional material:

[3] M. Rigo: Advanced Graph Theory and Combinatorics, Wiley-ISTE, 2016.

[4] B. Sudakov: Graph Theory (lecture notes), ETH Zürich, 2016.

Note:

Further information:

http://honza.ucw.cz/TG

Time-table for winter semester 2024/2025:

	06:00–08:0008:00–10:0010:00–12:0012:00–14:0014:00–16:0016:00–18:0018:00–20:0020:00–22:0022:00–24:00
Mon
Tue	roomTR:212 Volec J. 14:00–15:50 (lecture parallel1) Trojanova 13
Wed	roomTR:210 Volec J. 10:00–11:50 (lecture parallel1) Trojanova 13
Thu
Fri

Time-table for summer semester 2024/2025:

Time-table is not available yet

The course is a part of the following study plans: