The co-chromatic number of a graph $G$ is the smallest number t, such that $V(G)$ can be partitioned into $t$ cliques and stable sets.
Which graphs have bounded co-chromatic number? Let us say that a family $F$ of graphs is heroic if every graph $G$ with no induced subgraph isomorphic to a member of $F$ has bounded co-chromatic number (where the bound depends on $F$). Assuming an old conjecture of Gyarfas and Sumner, we can completely characterize all finite heroic families. This is joint work with Paul Seymour.
In joint work with Alex Scott and Paul Seymour, we have recently obtained a new proof of this result. The new proof relies on a more general theorem, that deals with excluding a pair of graphs $(H,J)$, such that $H$ and the complement of $J$ are disconnected.
In this talk we will explain this last result, as well as a few of its applications.