Efficiently coloring an arbitrary graph is a fundamental and notoriously difficult algorithmic problem. This talk focuses on the restricted problem of determining the complexity of coloring graphs which do not contain a certain induced subgraph. Combining results of Kaminski and Lozin, and Hoyler, it follows that this problem remains NP-complete unless the excluded induced subgraph is a disjoint union of paths.
Recently, as a first step towards resolving the general question, much work has been done to determine the complexity of coloring graphs which do not contain induced paths of a fixed length. Only one case remains open if we are allowed to use at least four colors: determining the complexity of four-coloring graphs with no induced six-vertex path.
The remaining, and most interesting, case is the problem of three-coloring graphs without long induced paths. Maria Chudnovsky, Mingxian Zhong, and I resolved the first open case for three-coloring: three-coloring graphs with no induced seven-vertex path can be done in polynomial time. Juraj Stacho and I have also made progress on the open four-coloring question.
In this talk, I will discuss some of the ideas and the general spirit of these structural coloring algorithms.