FLOC 2018: FEDERATED LOGIC CONFERENCE 2018
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: