Artykuł w czasopiśmie
Brak miniatury
Licencja

ClosedAccessDostęp zamknięty

Definable decompositions for graphs of bounded linear cliquewidth

Autor
Grohe, Martin
Pilipczuk, Michał
Bojańczyk, Mikołaj
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