1. Accueil
  2. EN
  3. Studying at ULB
  4. Find your course
  5. UE
INFO-F521

Graph theory

academic year
2024-2025

Course teacher(s)

Gwenaël JORET (Coordinator) and Yelena YUDITSKY

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. 
 

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

Yelena YUDITSKY - Campus Plaine - Département d'Informatique - Bâtiment NO (Yelena.Yuditsky@ulb.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

Programmes