I’ll speak about our project on H-free obstructions to 3-colorability.

Here, being H-free means that H is not an induced subgraph. We characterize all graphs H for which there are only finitely many 4-critical H-free graphs. We also characterize all graphs H for which there only finitely many obstructions to list 3-colorability. (In the list 3-colorability problem, each vertex is equipped with a subset of {1,2,3}, and may only receive colors from this list.)

I’ll mention some work in progress and an open problem.

Joint work with Maria Chudnovsky, Jan Goedgebeur and Mingxian Zhong.