AbstractDetermining 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 C4 and C2k+1 for all k ≥ 3. © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 2011