You are not logged in | Log in

PL /
EN

Speaker(s): Nikolas Mählmann
Affiliation: University of Warsaw
Language of the talk: English
Date: May 13, 2026, 2:15 p.m.
Room: room 5440
Title in Polish: Hereditary 2-WQO Graph Classes Have Bounded Clique-Width
Seminar: Seminar Automata Theory

A graph class is k-WQO if its k-labeled graphs are well-quasi-ordered under label-preserving induced subgraph embeddings.
We show that every hereditary graph class that is 2-WQO has bounded clique-width.
Combined with the recent result of Dumas and Lopez, this confirms a long-standing conjecture of Pouzet:
A hereditary graph class is 2-WQO if and only if it is k-WQO for all k >= 2.

This is joint work with Julien Duron and Szymon Toruńczyck.