Colouring Graphs Without a Subdivided H-Graph: A Full Complexity Classification

Abstract

We consider Colouring on graphs that are $H$-subgraph-free for some fixed graph $H$, which are graphs that do not contain $H$ as a subgraph. To classify the complexity of Colouring on $H$-subgraph-free graphs for connected $H$, it remains to consider when $H$ is a tree of maximum degree $4$ with exactly one vertex of degree $4$, or a tree of maximum degree $3$ with at least two vertices of degree $3$. We let $H$ be a so-called subdivided ``H''-graph, which is either a subdivided ${\mathbb{H}}_0$: a tree of maximum degree $4$ that is a star, or a subdivided ${\mathbb{H}}_1$: a tree of maximum degree $3$ with exactly two vertices of degree $3$. We develop new decomposition theorems resulting in polynomial-time algorithms, and in combination with known results, fully classify all cases ${\mathbb{H}}_0$ and ${\mathbb{H}}_1$. To illustrate the wider applicability of our techniques, we also employ them to obtain similar new polynomial-time results for two other classic graph problems: Stable Cut and, in part, Feedback Vertex Set.