Strengthening Rödl's theorem

Maria Chudnovsky, Alex Scott, Paul Seymour, Sophie Spirkl

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish (US)
Pages (from-to)256-271
Number of pages16
JournalJournal of Combinatorial Theory. Series B
Volume163
DOIs
StatePublished - Nov 2023

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Keywords

  • Induced subgraphs
  • Sparse graphs

Fingerprint

Dive into the research topics of 'Strengthening Rödl's theorem'. Together they form a unique fingerprint.

Cite this