Enseignant : Arnaud Casteigts
Assistants : Himika Das

Every Monday, room 301 (Battelle campus) - 11am (course) - 2pm (exercises).

Other pages for this class

Lecture notes

This section will be updated after each class.

  1. Basics of graph theory: [lecture notes]
  2. Basic algorithms: [lecture notes]
  3. Minimum Spanning Trees (and Matroid): [lecture notes]
  4. Computational complexity: [slides] - [lecture notes]
  5. Graph coloring: [slides]
  6. Maximum Matching: [lecture notes]
  7. Approximation algorithms: [lecture notes]
  8. Random Walks (and Markov chains): [slides]
  9. Distributed Algorithms: [slides]
  10. Basic Concepts of Temporal Graphs: [lecture notes]

Mini-class projects (in May 2026)

Objective: give a mini-class on a particular topic. Using slides is strongly recommended, possibly with hybrid content on the whiteboard.

Instructions: [slides]

Grading scale: 1/4 for this talk (+3/4 exam).

May 11 (course slot):

  • Freudiger: Graph coloring metaheuristics for production planning
  • Lin and Liu: Interval graphs (and who killed the duke of Densmore)
  • Kern and Khan: Cops and Robbers
  • von Düring: Centroid Decomposition
  • Kolikara: Page Rank

May 11 (exercise slot):

  • Slabe and Rasolfo: Graph Isomorphism
  • Zeller: GNN and Kirchoff’s Matrix
  • Jain: Ramsey Theory
  • Goulard and Papa: Brook’s Theorem
  • Zhang and Yang: Proof of Eulers Formula and degree 5 vertex

May 18 (course slot):

  • Vaskou : Graph Isomorphism
  • Alourou : Hamiltonian Path/Cycles
  • Amehunke: Proof of Eulers Formula and degree 5 vertex
  • Samb : Interval Graphs (and who killed the duke of Densmore)
  • Faizan Khan: Random Graph Models

May 18 (exercise slot):

  • Sedykh and Vanson: Tarjan’s Algorithm
  • Assadi: Population protocols
  • Camara: The Game of Hex and its connection to graph theory
  • Yaghi and Rakotomanana: Perfect Graphs
  • Souza Luz and Cavagna: Hamiltonian Paths/Cycles