***********************************
                * Princeton Discrete Math Seminar *
                ***********************************

Speaker: Oliver Schaudt (Köln)

Thursday 8th March, 3:00 in Fine Hall 224.

Title: When is a graph not 3-colorable?


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.

		---------------------------------------------

Next week:  Bernard Lidický

Anyone wishing to be added to or removed from this mailing list should
contact Paul Seymour (pds@math.princeton.edu)