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 C4 and C2k+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
- General Mathematics
- Computer Graphics and Computer-Aided Design
- Applied Mathematics