{"ID":2830820,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2512.09859","arxiv_id":"2512.09859","title":"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.","short_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 d...","url_abs":"https://arxiv.org/abs/2512.09859","url_pdf":"https://arxiv.org/pdf/2512.09859v2","authors":"[\"Tala Eagling-Vose\",\"Jorik Jooken\",\"Felicia Lucke\",\"Barnaby Martin\",\"Daniël Paulusma\"]","published":"2025-12-10T17:47:53Z","proceeding":"math.CO","tasks":"[\"math.CO\",\"cs.CC\",\"cs.DM\",\"cs.DS\"]","methods":"[]","has_code":false}