Marthe Bonamy : One (graph) minor to rule them all

par Marthe Bonamy (LaBRI)

jeudi 10 oct. 2024, 14:00 → 15:00 Europe/Paris

IHP

Robertson, Seymour and Thomas proved in 2006 that every planar graph on n vertices is a minor of the 2n*2n square grid. This theorem is notably convenient in proving that any graph not containing a given planar graph as a minor has bounded treewidth. After a gentle introduction to graph minors, I will discuss the equivalent of grids for classes other than planar graphs.