Obstructions for three coloring graphs with one forbidden induced subgraph
The complexity of coloring graphs without long induced paths is a notorious problem in algorithmic graph theory, an especially intruiging case being that of 3 colorability. So far, not much was known about certification in this context. 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 coloring 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.
SODA