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