### Abstract

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_{4} and C_{2k+1} for all k ≥ 3.

Original language | English (US) |
---|---|

Pages (from-to) | 100-120 |

Number of pages | 21 |

Journal | Random Structures and Algorithms |

Volume | 38 |

Issue number | 1-2 |

DOIs | |

State | Published - Jan 2011 |

### Keywords

- Critical graphs
- Extremal graphs
- Graph counting
- Structure of H-freegraphs

### ASJC Scopus subject areas

- Software
- Mathematics(all)
- Computer Graphics and Computer-Aided Design
- Applied Mathematics

## Fingerprint Dive into the research topics of 'Excluding induced subgraphs: Critical graphs'. Together they form a unique fingerprint.

## Cite this

Balogh, J., & Butterfield, J. (2011). Excluding induced subgraphs: Critical graphs.

*Random Structures and Algorithms*,*38*(1-2), 100-120. https://doi.org/10.1002/rsa.20353