Definable decompositions for graphs of bounded linear cliquewidth

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

## Paper Information

Title: | Definable decompositions for graphs of bounded linear cliquewidth |

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

Proceedings: | LICS PDF files |

Editors: | Anuj Dawar and Erich Grädel |

Keywords: | linear cliquewidth, transduction, definability, recognizability |

Abstract: | ABSTRACT. 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 clique 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. |

Pages: | 10 |

Talk: | Jul 09 11:00 (Session 47D) |

Paper: |