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

Unlike minors, the induced subgraph obstructions to bounded treewidth come ina large variety, including, for every $t\geq 1$, the $t$-basic obstructions:the graphs $K_{t+1}$ and $K_{t,t}$, along with the subdivisions of the$t$-by-$t$ wall and their line graphs. But this list is far from complete. Thesimplest example of a ''non-basic'' obstruction is due to Pohoata and Davies(independently). For every $n \geq 1$, they construct certain graphs oftreewidth $n$ and with no $3$-basic obstruction as an induced subgraph, whichwe call $n$-arrays.  Let us say a graph class $\mathcal{G}$ is clean if the only obstructions tobounded treewidth in $\mathcal{G}$ are in fact the basic ones. It follows thata full description of the induced subgraph obstructions to bounded treewidth isequivalent to a characterization of all families $\mathcal{H}$ of graphs forwhich the class of all $\mathcal{H}$-free graphs is clean (a graph $G$ is$\mathcal{H}$-free if no induced subgraph of $G$ is isomorphic to any graph in$\mathcal{H}$).  This remains elusive, but there is an immediate necessary condition: if$\mathcal{H}$-free graphs are clean, then there are only finitely many integers$n\geq 1$ such that there is an $n$-array which is $\mathcal{H}$-free. Theabove necessary condition is not sufficient in general. However, the situationturns out to be different if $\mathcal{H}$ is finite: we prove that for everyfinite set $\mathcal{H}$ of graphs, the class of all $\mathcal{H}$-free graphsis clean if and only if there is no $\mathcal{H}$-free $n$-array exceptpossibly for finitely many values of $n$.

Induced subgraphs and tree decompositions XIII. Basic obstructions in $\mathcal{H}$-free graphs for finite $\mathcal{H}$