Three-coloring graphs with no induced 6-edge paths

Maria Chudnovsky, Columbia University
Fine Hall 224

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. Results of Kaminski and Lozin, and Hoyler, show that the problem remains NP-complete unless H is a disjoint union of paths. Recently the complexity of coloring graphs with a fixed-length induced path forbidden has received considerable attention, and only a few cases of that problem remain open for k-coloring when k>=4. However, little is known for 3-coloring. Recently we have settled the first open case for 3-coloring; namely we showed that deciding 3-colorability for graphs with no induced 6-edge paths can be done in polynomial time. In this talk we will discuss some of the ideas of the algorithm. This is joint work with Peter Maceli and Mingxian Zhong.