## Paper: Definable Tree Decompositions (at LICS 2008)

**Martin Grohe**

### Abstract

We introduce a notion of definable tree decompositions of graphs. Actually, adefinable tree decomposition of a graph is not just a tree decomposition, but a more complicated structure that represents many different tree decompositions of the graph. It is definable in the graph by a tuple of formulas of some logic. In this paper, only study tree decomposition definable in fixed-point logic. We say that a definable tree decomposition is over a class of graphs if the pieces of the decomposition are in this class. We prove two general theorems lifting definability results from the pieces of a tree decomposition of a graph to the whole graph. Besides unifying earlier work on fixed-point definability and descriptive complexity theory on planar graphs and graphs of bounded tree width, these general results can be used to prove that the class of all graphs without a K_5-minor is definable infixed-point logic and that fixed-point logic with counting captures polynomialtime on this class.

### BibTeX

@InProceedings{Grohe-DefinableTreeDecomp, author = {Martin Grohe}, title = {Definable Tree Decompositions}, booktitle = {Proceedings of the Twenty-Third Annual IEEE Symposium on Logic in Computer Science (LICS 2008)}, year = {2008}, month = {June}, pages = {406--417}, location = {Pittsburgh, PA, USA}, publisher = {IEEE Computer Society Press} }