Artykuł w czasopiśmie
Brak miniatury
Licencja
Definable decompositions for graphs of bounded linear cliquewidth
Autor
Data publikacji
2021
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