Definable decompositions for graphs of bounded linear cliquewidthArticle
Authors: Mikołaj Bojańczyk ; Martin Grohe ; Michał Pilipczuk
NULL##NULL##0000-0001-7891-1988
Mikołaj Bojańczyk;Martin Grohe;Michał Pilipczuk
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.
A unified theory of finite-state recognisability; Funder: European Commission; Code: 683080
Bibliographic References
1 Document citing this article
Martin Grohe;Daniel Neuen, 2022, Canonisation and Definability for Graphs of Bounded Rank Width, arXiv (Cornell University), 24, 1, pp. 1-31, 10.1145/3568025, https://arxiv.org/abs/1901.10330.