9 mai 2016

Selma Djelloul Naboulsi (UPEC)

At the beginning of the 1990’s, researchers in algorithmic graph theory (re)discovered under different formalisms the notion of treewidth of a graph and its impact on parameterized complexity of many hard problems of graph theory. This gave rise to a flourishing literature by researchers from different fields. Indeed, tree-decompositions are used to describe deep structural properties of classes of graphs as well as to design FPT-algorithms. These are the most known ways treewidth is dealt with. In this talk, we focus on another field where treewidth hides, and which is less known than the previously mentioned two fields. More precisely, we present how algebras of graphs can be defined, how a graph can be viewed as the value of a term over a signature, and how the components of the least solution of a polynomial system over a signature can be related to sets of graphs with bounded treewidth.