Hereditary 2-WQO Graph Classes Have Bounded Clique-Width

Prelegent(ci)

Nikolas Mählmann

Afiliacja

University of Warsaw

Język referatu

angielski

Termin

13 maja 2026 14:15

Pokój

p. 5440

Tytuł w języku polskim

Hereditary 2-WQO Graph Classes Have Bounded Clique-Width

Seminarium

Seminarium „Teoria automatów”

---

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.

---