User Tools

Site Tools


Peter Maceli (Columbia)

Coloring Graphs with Forbidden Induced Subgraphs

Abstract for the Combinatorics Seminar 2014 April 22

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.

seminars/comb/abstract.201404mac.txt · Last modified: 2020/01/29 14:03 (external edit)