Open Collections

Description

The problem of testing if a graph can be colored with a given number $k$ of colors is NP-complete for every $k>2$. But what if we have more information about the input graph, namely that some fixed graph $H$ is not present in it as an induced subgraph? It is known that the problem remains NP-complete even for $k=3$, unless $H$ is the disjoint union of paths. We consider the following two questions: 1. For which graphs $H$ is there a polynomial time algorithm to 3-color (or in general $k$-color) an $H$-free graph? 2. For which graphs $H$ are there finitely many 4-critical $H$-free graphs?  This talk will survey recent progress on these questions, and in particular give a complete answer to the second one.