Skip to content
Preprint

Obstructions to $k$-colouring $H$-free graphs

Oct 2026 · 0 citations · 39 references
Mathematics Computer Science

Abstract

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 $\chi(G)=k+1$ but $\chi(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 and only if $H$ is an induced subgraph of $P_4+\ell P_1$ for some $\ell \geq 0$.

View source

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.