« search calendars« CoSP Workshop and School on Algorithms and Complexity

« Coloring Graphs with a Forbidden Induced Subgraph

Coloring Graphs with a Forbidden Induced Subgraph

July 16, 2019, 11:20 AM - 12:50 PM


Hill Center, Room 116

Rutgers University

Sophie Spirkl, Rutgers University

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.)