Definable decompositions for graphs of bounded linear cliquewidth
Authors: Mikołaj Bojańczyk, Martin Grohe and Michał Pilipczuk
Paper Information
Title: | Definable decompositions for graphs of bounded linear cliquewidth |
Authors: | Mikołaj Bojańczyk, Martin Grohe and Michał Pilipczuk |
Proceedings: | LICS PDF files |
Editors: | Anuj Dawar and Erich Grädel |
Keywords: | linear cliquewidth, transduction, definability, recognizability |
Abstract: | ABSTRACT. We prove that for every positive integer k, there exists an MSO_1-transduction that given a graph of linear cliquewidth at most k 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 CMSO_1-definability and recognizability on graphs of bounded linear cliquewidth. |
Pages: | 10 |
Talk: | Jul 09 11:00 (Session 47D) |
Paper: |