The Global Structure of a Typical Graph Without $H$ as an Induced Subgraph when $H$ is a Cycle

Bruce Reed

One way to certify that a graph does not contain an induced cycle of length six is to provide a partition of its vertex set into (i) a stable set, and (ii) a graph containing no st…