Induced subgraph density. III. Cycles and subdivisions

arXiv2307.06379MaRDI QIDQ6511048FDOQ6511048

Authors: Tung D. Nguyen, Alex Scott, Paul Seymour 

Abstract: A theorem of R"odl says that for every graph $H$, and every $varepsilon>0$, there exists $delta>0$ such that if $G$ is a graph that has no induced subgraph isomorphic to $H$, then there exists $XsubseteqV(G)$ with $|X|gedelta|G|$ such that one of $G[X],overlineG[X]$ has at most $$ edges. But for fixed $H$, how does $delta$ depends on $varepsilon$? If the dependence is polynomial, then $H$ satisfies the ErdH{o}s-Hajnal conjecture; and Fox and Sudakov conjectured that the dependence is polynomial for {em every} graph $H$. This conjecture is substantially stronger than the ErdH{o}s-Hajnal conjecture itself, and until recently it was not known to be true for any non-trivial graphs $H$. The preceding paper of this series showed that it is true for $P_4$, and all graphs obtainable from $P_4$ by vertex-substitution. Here we will show that the Fox-Sudakov conjecture is true for all the graphs $H$ that are currently known to satisfy the ErdH{o}s-Hajnal conjecture. In other words, we will show that it is true for the bull, and the 5-cycle, and induced subgraphs of them, and all graphs that can be obtained from these by vertex-substitution. There is a strengthening of R"odl's theorem due to Nikiforov, that replaces the hypothesis that $G$ has no induced subgraph isomorphic to $H$, with the weaker hypothesis that the density of induced copies of $H$ in $G$ is small. We will prove the corresponding ``polynomial strengthening of Nikiforov's theorem for the same class of graphs $H$.

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Density (toughness, etc.) (05C42)

This page was built for publication: Induced subgraph density. III. Cycles and subdivisions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6511048)