Forbidden Induced Subgraphs and the Ɓoƛ-Tarski Theorem

08/02/2020
∙
by   Yijia Chen, et al.
∙
0
∙

Let 𝒞 be a class of finite and infinite graphs that is closed under induced subgraphs. The well-known Ɓoƛ-Tarski Theorem from classical model theory implies that 𝒞 is definable in first-order logic (FO) by a sentence φ if and only if 𝒞 has a finite set of forbidden induced finite subgraphs. It provides a powerful tool to show nontrivial characterizations of graphs of small vertex cover, of bounded tree-depth, of bounded shrub-depth, etc. in terms of forbidden induced finite subgraphs. Furthermore, by the Completeness Theorem, we can compute from φ the corresponding forbidden induced subgraphs. We show that this machinery fails on finite graphs. - There is a class 𝒞 of finite graphs which is definable in FO and closed under induced subgraphs but has no finite set of forbidden induced subgraphs. - Even if we only consider classes 𝒞 of finite graphs which can be characterized by a finite set of forbidden induced subgraphs, such a characterization cannot be computed from an FO-sentence φ, which defines 𝒞, and the size of the characterization cannot be bounded by f(|φ|) for any computable function f. Besides their importance in graph theory, the above results also significantly strengthen similar known results for arbitrary structures.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset