A theorem of Rödl states that for every fixed $F$ and $\varepsilon>0$ there is $\delta=\delta_F(\varepsilon)$ so that every induced $F$-free graph contains a vertex set of size $\delta n$ whose edge density is either at most $\varepsilon$ or at least $1-\varepsilon$. Rödl's proof relied on the regularity lemma, hence it supplied only a tower-type bound for $\delta$. Fox and Sudakov conjectured that $\delta$ can be made polynomial in $\varepsilon$, and a recent result of Fox, Nguyen, Scott and Seymour shows that this conjecture holds when $F=P_4$. In fact, they show that the same conclusion holds even if $G$ contains few copies of $P_4$. In this note we give a short proof of a more general statement.
@article{10_37236_12189,
author = {Lior Gishboliner and Asaf Shapira},
title = {On {R\"odl's} theorem for cographs},
journal = {The electronic journal of combinatorics},
year = {2023},
volume = {30},
number = {4},
doi = {10.37236/12189},
zbl = {1532.05096},
url = {http://geodesic.mathdoc.fr/articles/10.37236/12189/}
}
TY - JOUR
AU - Lior Gishboliner
AU - Asaf Shapira
TI - On Rödl's theorem for cographs
JO - The electronic journal of combinatorics
PY - 2023
VL - 30
IS - 4
UR - http://geodesic.mathdoc.fr/articles/10.37236/12189/
DO - 10.37236/12189
ID - 10_37236_12189
ER -
%0 Journal Article
%A Lior Gishboliner
%A Asaf Shapira
%T On Rödl's theorem for cographs
%J The electronic journal of combinatorics
%D 2023
%V 30
%N 4
%U http://geodesic.mathdoc.fr/articles/10.37236/12189/
%R 10.37236/12189
%F 10_37236_12189
Lior Gishboliner; Asaf Shapira. On Rödl's theorem for cographs. The electronic journal of combinatorics, Tome 30 (2023) no. 4. doi: 10.37236/12189
