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

For any finite set $\mathcal{H} = \{H_1,\ldots,H_p\}$ of graphs, a graph is$\mathcal{H}$-subgraph-free if it does not contain any of $H_1,\ldots,H_p$ as asubgraph. In recent work, meta-classifications have been studied: these showthat if graph problems satisfy certain prescribed conditions, their complexityis determined on classes of $\mathcal{H}$-subgraph-free graphs. We continuethis work and focus on problems that have polynomial-time solutions on classesthat have bounded treewidth or maximum degree at most~$3$ and examine theircomplexity on $H$-subgraph-free graph classes where $H$ is a connected graph.With this approach, we obtain comprehensive classifications for (Independent)Feedback Vertex Set, Connected Vertex Cover, Colouring and Matching Cut. Thisresolves a number of open problems.  We highlight that, to establish that Independent Feedback Vertex Set belongsto this collection of problems, we first show that it can be solved inpolynomial time on graphs of maximum degree $3$. We demonstrate that, with theexception of the complete graph on four vertices, each graph in this class hasa minimum size feedback vertex set that is also an independent set.

Complexity Framework for Forbidden Subgraphs III: When Problems are Tractable on Subcubic Graphs