Graph Theory
Code  Completion  Credits  Range 

PITGR  ZK  4  2+1 
 Lecturer:
 Ondřej Suchý (guarantor), Tomáš Valla
 Tutor:
 Jan Kratochvíl (guarantor), Ondřej Suchý (guarantor), Tomáš Valla
 Supervisor:
 Department of Theoretical Computer Science
 Synopsis:

Attention will be paid both to structural issues and to questions of algorithmization and computational complexity of basic optimization problems restricted to special graph classes, aiming at determining the boundary between polynomially solvable and NPhard variants of the problems.
 Requirements:

General knowledge of discrete mathematics and efficient algorithms.
 Syllabus of lectures:

1. Network Flows
2. Applications of network flows  higher connectivity of graphs, FordFulkerson and Menger Theorem, Hall's Marriage Theorem
3. Matching in graphs
4. Planar graphs  Kuratowski Theorem, 5 Color Theorem
5. Chromatic number and colorings of graphs
6. Hamiltonian graphs
7. Minors and their algorithmic usage
8. Dynamic programming on trees and grids, path and tree decompositions and basic properties
9. Dynamic programming on tree decompositions
10. MSOL, Courcelle Theorem and an alternative characterization of tree width
11. Computing tree width, tree width of planar graphs and algorithms for planar graphs, bidimensionality
12. Baker's shifitng technique, decopositions of dense graphs
 Syllabus of tutorials:
 Study Objective:

Overview of modern methods of graph theory.
 Study materials:

1. R. Diestel, Graph Theory, 5th edition, Springer, 2017.
2. Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh, Parameterized Algorithms, Springer 2015.
3. Downey, Rodney G., Fellows, Michael R.: Fundamentals of Parameterized Complexity, Springer, 2013.
 Note:
 Further information:
 https://courses.fit.cvut.cz/PITGR/
 Timetable for winter semester 2018/2019:
 Timetable is not available yet
 Timetable for summer semester 2018/2019:
 Timetable is not available yet
 The course is a part of the following study plans:

 Informatics (VO)