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

Graph theory

academic year
2023-2024

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. 
 

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

Programmes