1. Mikołaj Bojańczyk, Michal Pilipczuk
   Definability equals recognizability for graphs of bounded treewidth. LICS, 2016   PDF

2. Mikołaj Bojańczyk, Michal Pilipczuk
   Optimizing Tree Decompositions in MSO. STACS, 2017   PDF

3. Mikołaj Bojańczyk
   Two monads for graphs. CoRR, 2018   PDF

In paper [1] (see also the arxiv version and these slides) we show that for every there is an MSO transduction, which inputs a graph of tree width at most , and outputs a tree decomposition of width at most . The transduction is nondeterministic, which means it might output several possible tree decompositions, but at least one. A corollary of this result is that a conjecture of Courcelle is true: for languages of graphs of bounded tree width, definability in MSO is equivalent to recognisability.

In paper [2], we show that for every there is an MSO transduction which inputs a width tree decomposition and outputs an optimal width tree decomposition of the same graph. Combining these two results, we see that for every there is an MSO transduction which maps graphs of treewidth to their optimal width tree decompositions.

Paper [3] uses the terminology of monads to describe recognisable languages of graphs. This is meant as an alternative description of Courcelle’s VR and HR recognisable graph classes. The paper also has a new result, namely it is decidable if an CMSO definable languages of graphs (of bounded treewidth) can be defined in MSO (i.e. it is decidable if the counting, which is the C in CMSO, is necessary).