2021/05/16 by Maria Chudnovsky, Alex Scott, Chudnovsky, Maria +5
Computer Science · Mathematics · #Advanced Graph Theory Research #Advanced Topology and Set Theory #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2105.07370
openalex publication_date 2021/05/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.