Title: Coloring Graphs with Forbidden Induced Subgraphs
Speaker: Maria Chudnovsky, Columbia University
Date: Wednesday, February 12, 2014 2:00pm
Location: Hill Center, Room 525, Rutgers University, Busch Campus, Piscataway, NJ
Since graph-coloring is an NP-complete problem in general, it is natural to ask how the complexity changes if the input graph is known not to contain a certain induced subgraph H. Due to results of Kaminski and Lozin, and Hoyler, the problem remains NP-complete, unless H is the disjoint union of paths. Recently the question of coloring graphs with a fixed-length induced path forbidden has received considerable attention. Only one case of that problem remains open for k-coloring when k>=4, and that is the case of 4-coloring graphs with no induced 6-vertex path. However, little is known for 3-coloring. Recently we settled the first open case for 3-coloring; namely we showed that 3-coloring graphs with no induced 7-vertex paths can be done in polynomial time. We also made progress on the 4-coloring question. In this talk we will discuss some of the ideas of the algorithms. This is joint work with Peter Maceli, Juraj Stacho and Mingxian Zhong.
See: http://math.rutgers.edu/seminars/allseminars.php?sem_name=Discrete%20Math