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

Matthew Johnson, Barnaby Martin, Sukanya Pandey +3

For any finite set $\mathcal{H}=\{H_1,\dots ,H_p\}$ of graphs, a graph is $\mathcal{H}$-subgraph-free if it does not contain any of $H_1,\dots ,H_p$ as a subgraph. In recent work…