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/

Zendy Open

Presents the pdf analysis as premium feature

PDF Analysis

Insights

Presents the summarisation as premium feature

Summarisation

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

A theta is a graph formed by three paths between the same pair of distinctvertices so that the union of any two of the paths induces a hole. A wheel is agraph formed by a hole and a node that has at least 3 neighbors in the hole. Inthis paper we obtain a decomposition theorem for the class of graphs that donot contain an induced subgraph isomorphic to a theta or a wheel, i.e. theclass of (theta, wheel)-free graphs. The decomposition theorem uses cliquecutsets and 2-joins. Clique cutsets are vertex cutsets that work really well indecomposition based algorithms, but are unfortunately not general enough todecompose more complex hereditary graph classes. A 2-join is an edge cutsetthat appeared in decomposition theorems of several complex classes, such asperfect graphs, even-hole-free graphs and others. In these decompositiontheorems 2-joins are used together with vertex cutsets that are more generalthan clique cutsets, such as star cutsets and their generalizations (which aremuch harder to use in algorithms). This is a first example of a decompositiontheorem that uses just the combination of clique cutsets and 2-joins. This hasseveral consequences. First, we can easily transform our decomposition theoreminto a complete structure theorem for (theta, wheel)-free graphs, i.e. we showhow every (theta, wheel)-free graph can be built starting from basic graphsthat can be explicitly constructed, and gluing them together by prescribedcomposition operations; and all graphs built this way are (theta, wheel)-free.Such structure theorems are very rare for hereditary graph classes, only a fewexamples are known. Secondly, we obtain an $\mathcal O (n^4m)$-timedecomposition based recognition algorithm for (theta, wheel)-free graphs.Finally, in Parts III and IV of this series, we give further applications ofour decomposition theorem.

The (theta, wheel)-free graphs Part II: structure theorem