For several graph classes without long induced paths there exists a finite forbidden subgraph characterization for k-colourability. Such a finite set of minimal obstructions allows to provide a “no-certificate" which proves that a graph is not k-colourable.

We prove that there are only finitely many 4-critical P6-free graphs, and give the complete list that consists of 24 graphs. In particular, we obtain a certifying algorithm for 3-colouring P6-free graphs, which solves an open problem posed by Golovach et al. (Here, P6 denotes the induced path on six vertices.)

Our result leads to the following dichotomy theorem: if H is a connected graph, then there are finitely many 4-critical H-free graphs if and only if H is a subgraph of P6. This answers a question of Seymour.

The proof of our main result involves two distinct automatic proofs, and an extensive structural analysis by hand.

In this talk we will mainly focus on the algorithmic results by presenting a new algorithm for generating all minimal forbidden subgraphs to k-colourability for given graph classes. This algorithm (combined with new theoretical results) has been successfully applied to fully characterise all forbidden subgraphs for k-colourability for various classes of graphs without long induced paths.

(This is joint work with Maria Chudnovsky, Oliver Schaudt and Mingxian Zhong.)