Sophie Spirkl, Rutgers University

Abstract

What is the complexity of k-coloring graphs that do not contain a fixed graph H as an induced subgraph? It turns out that we can restrict our attention to the case when H is an induced subgraph of a path. I will talk about some recent results and open questions in this area. This is based on joint work with Maria Chudnovsky and Mingxian Zhong. 

Video This is a video of a talk given on a blackboard. (The sound is a little low, so you may need to increase the volume.)