Videos

Coloring Graphs with Forbidden Induced Subgraphs

Presenter
September 10, 2014
Keywords:
  • Coloring Graphs
MSC:
  • 05C15
Abstract
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.