Excluding induced subgraphs: Critical graphs

Determining the cardinality and describing the structure of H-free graphs is well-investigated for many graphs H. In the nineties, Prömel and Steger proved that for a graph H with chromatic number k + 1 almost all graphs not containing H as a subgraph are k-colorable if and only if H contains a color-critical edge. We strengthen the concept of H-free to induced subgraph containment, proving that if H has coloring number k + 1 then almost all H-free graphs can be covered by k graphs that are cliques or independent sets if and only if H is in some well-defined sense critical. The family of critical graphs includes C₄ and C_2k+1 for all k ≥ 3.