Graph coloring is a classical problem in mathematics where you assign colors to the vertices of a graph so that no two connected vertices share the same color. The minimum number of colors needed is called the chromatic number. A key related concept is a "minimal obstruction" to k-coloring: a graph that cannot be colored with k colors, but if you remove any single vertex, it suddenly can be. Understanding these minimal obstructions tells you exactly what structures make a graph hard to color. This paper focuses on a restricted setting where the graphs are "H-free," meaning they are forbidden from containing a particular smaller graph H as an induced subgraph.
A 2020 result by Chudnovsky and collaborators settled when there are only finitely many minimal obstructions to 3-coloring among H-free graphs. Having finitely many obstructions is desirable because it can make the coloring problem more tractable. The new paper extends this line of work to k-coloring for any k greater than 4, asking the same basic question: for which forbidden graphs H does the collection of minimal obstructions stay finite?
The main result gives a clean and complete answer. For any k greater than 4, there are only finitely many minimal obstructions to k-coloring among H-free graphs if and only if H is an induced subgraph of a specific simple family of graphs, namely a path on four vertices together with some number of isolated vertices. This characterization is tight and elegant, drawing a sharp dividing line between the cases where the obstruction landscape is manageable and where it explodes into infinitely many examples.