Course teacher(s)
Gwenaël JORET (Coordinator)ECTS credits
5
Language(s) of instruction
english
Course content
Introductory course to graph theory. Topics covered include:
- Matchings in bipartite and non-bipartite graphs;
- Connectivity (Menger's theorem, the structure of 2- and 3-connected graphs);
- Planar graphs (plane graphs, Euler's formula, Kuratowski's theorem);
- Coloring (coloring planar graphs, vertex- and edge-colorings, perfect graphs);
- Structural graph theory (treewidth, minors);
- Extremal graph theory;
- Random graphs;
- The probabilistic method.
- Matchings in bipartite and non-bipartite graphs;
- Connectivity (Menger's theorem, the structure of 2- and 3-connected graphs);
- Planar graphs (plane graphs, Euler's formula, Kuratowski's theorem);
- Coloring (coloring planar graphs, vertex- and edge-colorings, perfect graphs);
- Structural graph theory (treewidth, minors);
- Extremal graph theory;
- Random graphs;
- The probabilistic method.
Objectives (and/or specific learning outcomes)
Graphs are simple and ubiquitous structures. The course aims at providing the student with the basics of graph theory, in a mathematically sound way.
Teaching methods and learning activities
Lectures (24h), exercise sessions (12h), and two homeworks.
References, bibliography, and recommended reading
Reinhard Diestel, Graph Theory, Graduate Texts in Mathematics 173. Published by Springer. Available online here: https://diestel-graph-theory.com/
Other information
Contacts
Gwenaël JORET - Campus Plaine - Département d'Informatique - CP212 Bâtiment N/O, bureau 2.O8.111 (gjoret@ulb.ac.be)
Campus
Plaine
Evaluation
Method(s) of evaluation
- written examination
written examination
Homeworks + written exam on theory and exercises.
Mark calculation method (including weighting of intermediary marks)
Homeworks: 4 points
Written exam: 16 points (half theory - half exercices)
Language(s) of evaluation
- english