KAIST

**4PM-5PM**

Room 1409

In this talk, we present a result that for every graph G that is vertex-minor minimal with the property having linear rank-width larger than p, the number of vertices in G is at most doubly exponential in \(\mathcal{O}(p)\). The number of vertex-minor obstructions for linear rank-width at most p is of interest because the only known fixed parameter tractable algorithm to test whether linear rank-width is at most p is using the finiteness of the number of forbidden vertex-minor obstructions. Our result gives an upper bound of the complexity on this algorithm. Our basic tools are the algebraic operations on labelled graphs introduced by Kanté and Rao, and we extend the notion of vertex-minors in our purpose. This is joint work with Mamadou Moustapha Kanté.