When is a graph not 3colorable?
When is a graph not 3colorable?

Oliver Schaudt, University of Cologne
Fine Hall 224
I’ll speak about our project on Hfree obstructions to 3colorability.
Here, being Hfree means that H is not an induced subgraph. We characterize all graphs H for which there are only finitely many 4critical Hfree graphs. We also characterize all graphs H for which there only finitely many obstructions to list 3colorability. (In the list 3colorability 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.