joint work with Martin Grohe, and Michał Pilipczuk

Speaker(s)

Mikołaj Bojańczyk

Affiliation

Uniwersytet Warszawski

Date

March 15, 2017, 2:15 p.m.

Room

room 5870

Title in Polish

Definable decompositions for graphs of bounded linear clique width

Seminar

Seminar Automata Theory

---

We prove that for every positive integer k, there exists an mso1-transduction which inputs a graph of linear cliquewidth at most k and outputs, nondeterministically, some clique decomposition of the graph of width bounded by a function of k. A direct corollary of this result is the equivalence of the notions of cmso1-definability and recognizability on graphs of bounded linear cliquewidth.

---