Graphs of unbounded linear cliquewidth.

Speaker(s)

Mikołaj Bojańczyk

Affiliation

University of Warsaw

Language of the talk

English

Date

Jan. 15, 2025, 2:15 p.m.

Room

room 5440

Title in Polish

Graphs of unbounded linear cliquewidth.

Seminar

Seminar Automata Theory

---

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)

---