| Summary: | What can be said about the structure of graphs that do not
contain an induced copy of some graph H? Rödl showed in the
1980s that every H-free graph has large parts that are very
sparse or very dense. More precisely, let us say that a graph F
on n vertices is ε-restricted if either F or its complement has
maximum degree at most εn. Rödl proved that for every graph
H, and every ε > 0, every H-free graph G has a linear-sized
set of vertices inducing an ε-restricted graph. We strengthen
Rödl’s result as follows: for every graph H, and all ε > 0,
every H-free graph can be partitioned into a bounded number
of subsets inducing ε-restricted graphs.
|
|---|