English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Let $\mathscr C$ be a class of finite and infinite graphs that is closedunder induced subgraphs. The well-known {\L}o\'s-Tarski Theorem from classicalmodel theory implies that $\mathscr C$ is definable in first-order logic (FO)by a sentence $\varphi$ if and only if $\mathscr C$ has a finite set offorbidden induced finite subgraphs. It provides a powerful tool to shownontrivial characterizations of graphs of small vertex cover, of boundedtree-depth, of bounded shrub-depth, etc. in terms of forbidden induced finitesubgraphs. Furthermore, by the Completeness Theorem, we can compute from$\varphi$ the corresponding forbidden induced subgraphs. We show that thismachinery fails on finite graphs.  - There is a class $\mathscr C$ of finite graphs which is definable in FO andclosed under induced subgraphs but has no finite set of forbidden inducedsubgraphs.  - Even if we only consider classes $\mathscr C$ of finite graphs which can becharacterized by a finite set of forbidden induced subgraphs, such acharacterization cannot be computed from an FO-sentence $\varphi$, whichdefines $\mathscr C$, and the size of the characterization cannot be bounded by$f(|\varphi|)$ for any computable function $f$.  Besides their importance in graph theory, the above results alsosignificantly strengthen similar known results for arbitrary structures.

Forbidden Induced Subgraphs and the {\L}o\'s-Tarski Theorem