Graphs of unbounded linear cliquewidth.

Prelegent(ci)

Mikołaj Bojańczyk

Afiliacja

University of Warsaw

Język referatu

angielski

Termin

15 stycznia 2025 14:15

Pokój

p. 5440

Tytuł w języku polskim

Graphs of unbounded linear cliquewidth.

Seminarium

Seminarium „Teoria automatów”

---

We show that for every class C of graphs, one of the following holds:
1. The class has bounded linear cliquewidth; or
2. There is a surjective MSO transduction from C to the class of all trees.
This is a dense counterpart of a similar result for sparse graphs, where it was previously known that if a class of graphs has unbounded treewidth, then it contains all trees as graph minors.

(Joint work with Pierre Ohlmann)

---