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).
References, bibliography, and recommended reading
Reinhard Diestel, Graph Theory, Graduate Texts in Mathematics 173. Published by Springer. Available online for ULB students for free (need to be connected to the ULB network): https://link.springer.com/book/10.1007/978-3-662-70107-2
Other information
Contacts
Gwenaël JORET - Campus Plaine - Département d'Informatique - Bâtiment NO (gwenael.joret@ulb.be)
Campus
Plaine
Evaluation
Method(s) of evaluation
- written examination
written examination
Written exam on theory and exercises.
Mark calculation method (including weighting of intermediary marks)
Written exam: 20 points (half theory - half exercices)
Language(s) of evaluation
- english