14:00
15:00

Title: Simon's Factorisation in graph theory

Abstract: This talk aims to give an overview of the applications of automata
theory to graphs of small tree-width or clique-width, and particularly
the use of Simon's Factorisation Forests Theorem.

A first part will focus on MSO definable decompositions, which were the
first application of Simon's theorem in graph theory, by Bojańczyk and
Pilipczuk. I will explain the context of this problem, the grand lines
of their proof, some recent variants of their result, and remaining open
questions.

I will conclude with a few more graph theoretic problems for which
Simon's theorem proves equally useful, such as finding proper
colourings, and minimal obstructions to some structures.

Français
178