{"id":"arxiv/2610.10737","url":"https://arxiv.org/abs/2610.10737","tags":["math.CO","cs.DM"],"score":0,"title":"Obstructions to $k$-colouring $H$-free graphs","domain":"math.CO","source":"arxiv","authors":["Iain Beaton","Ben Cameron","Adam van Omme"],"reviews":0,"subject":"math.CO","summary":"A graph is $H$-free if it has no induced subgraph isomorphic to $H$. In 2020, Chudnovsky, Goedgebeur, Schaudt, and Zhong characterized all graphs $H$ such that there are only finitely many minimal obstructions to $3$-colouring $H$-free graphs. In general, the minimal obstructions to $k$-colouring $H$-free graphs are the $(k+1)$-vertex-critical $H$-free graphs, those are, the $H$-free graphs $G$ with $χ(G)=k+1$ but $χ(G-v)=k$ for every vertex in $G$. In this paper we complete the characterization for all $k > 4$ by showing that there are onky finitely $k$-vertex-critical $H$-free graphs if…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-10-07","reactions":{}}