Bojańczyk, Mikołaj and Grohe, Martin and Pilipczuk, Michał - Definable decompositions for graphs of bounded linear cliquewidth

lmcs:5295 - Logical Methods in Computer Science, January 25, 2021, Volume 17, Issue 1
Definable decompositions for graphs of bounded linear cliquewidth

Authors: Bojańczyk, Mikołaj and Grohe, Martin and Pilipczuk, Michał

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 cliquewidth 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.


Volume: Volume 17, Issue 1
Published on: January 25, 2021
Submitted on: March 20, 2019
Keywords: Computer Science - Logic in Computer Science


Share

Consultation statistics

This page has been seen 83 times.
This article's PDF has been downloaded 105 times.