Coloring Graphs with Forbidden Induced Subgraphs

Wednesday, September 10, 2014 - 10:15am - 11:05am
Keller 3-180
Maria Chudnovsky (Columbia University)
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, and related problems.

This is joint work with Peter Maceli, Juraj Stacho and Mingxian Zhong.
MSC Code: