Definable decompositions for graphs of bounded linear cliquewidth
Definable decompositions for graphs of bounded linear cliquewidth
Autor
Punktacja ministerialna
70
Data publikacji
Abstrakt (EN)
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.
Dyscyplina PBN
informatyka
Czasopismo
Logical Methods in Computer Science
Tom
17
Zeszyt
1
Strony od-do
1-40
ISSN
1860-5974
Licencja otwartego dostępu
Dostęp zamknięty