Strengthening Rödl's theorem

TY - JOUR

T1 - Strengthening Rödl's theorem

AU - Chudnovsky, Maria

AU - Scott, Alex

AU - Seymour, Paul

AU - Spirkl, Sophie

N1 - Publisher Copyright: © 2023 The Authors

PY - 2023/11

Y1 - 2023/11

N2 - 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.

AB - 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.

KW - Induced subgraphs

KW - Sparse graphs

UR - http://www.scopus.com/inward/record.url?scp=85172172244&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85172172244&partnerID=8YFLogxK

U2 - 10.1016/j.jctb.2023.07.004

DO - 10.1016/j.jctb.2023.07.004

M3 - Article

SN - 0095-8956

VL - 163

SP - 256

EP - 271

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

ER -