Hereditary 2-WQO Graph Classes Have Bounded Clique-Width

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.

---