$H$-free and $\mathcal{F}$-free graphs under the induced-subgraph convention

Depends on

• Induced embeddings and induced copies of a graph
• The induced-embedding count $\operatorname{ind}_H(G)$

Used by

• An H-free graph has a linearly large induced subgraph whose graph or complement has bounded maximum degree Corollary
• Every graph on at most three vertices has the Erdős–Hajnal property Corollary
• Every P₄-free graph has a clique or stable set of size at least the square root of its order Corollary
• For a single graph, the Erdős–Hajnal property, the polynomial Rödl property, and virality are equivalent Corollary
• For every λ>0 a bounded number of disjoint ε-restricted sets covers all but λ|V(G)| vertices of an H-free graph Corollary
• G is H-free if and only if Ḡ is H̄-free Corollary
• Rödl: for every H and every ε∈(0,1/2) there is δ>0 such that every nonempty H-free graph has an ε-restricted vertex set of size at least δ|V(G)| Corollary
• Rödl's theorem for a nonempty family of forbidden induced subgraphs Corollary
• The polynomial Rödl property implies the Erdős–Hajnal property Corollary
• The seven-cycle and its complement have the Erdős-Hajnal property Corollary
• The singleton family {E} has property (*) Corollary
• The six-cycle and its complement have the Erdős-Hajnal property Corollary
• The viral property implies the polynomial Rödl property Corollary
• The dense alternative in Rödl's theorem cannot be dropped Counterexample
• The empty forbidden family is not Erdős–Hajnal Counterexample
• The polynomial Rödl witness need not be the whole graph Counterexample
• A bull-free graph Definition
• A nice graph Definition
• Generalized nice finite graph families Definition
• Leaf-reducible finite graph families Definition
• Minimal forbidden induced subgraphs and forbidden bases Definition
• Property (*) for a finite graph family Definition
• The polynomial Rödl property for a finite forbidden family Definition
• The structural comb-partition hypothesis Definition
• The viral property for a finite forbidden family Definition
• Wonderful finite graph families Definition
• A graph is P₃-free if and only if every connected component is complete Example
• For P₃-free graphs Rödl's theorem holds with δ=ε, by an explicit argument Example
• A large cy-restricted subgraph in the three-outcome theorem forces a smaller-scale restricted subgraph Lemma
• An induced copy of H₂ inside the extension set of an induced embedding of H₁-v yields an induced copy of H₁ with H₂ substituted for v Lemma
• Every class defined by forbidden induced subgraphs is hereditary Lemma
• Every induced subgraph of an F-free graph is F-free Lemma
• If ε is an Erdős–Hajnal constant for H and W is a nonempty vertex set with |W|^ε>hom(G), then G[W] has an induced copy of H Lemma
• Leaf-reducible families yield a large anticomplete pair or a deeper restricted induced subgraph Lemma
• Small total induced-copy expectation forces many homogeneous k-sets Lemma
• The edge-plus-isolate co-Bird obstruction Lemma
• The family consisting of H₅ and co-E has the Erdős–Hajnal property Lemma
• The path-plus-isolate co-Bird obstruction Lemma
• A minimal counterexample to a kappa-bound is tau-critical Proposition
• If H is an induced subgraph of H' and H' has the Erdős–Hajnal property, then H has it with every constant of H' Proposition

…and 21 more results.

Dependency tree · two levels

9 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

• Valerio Boncompagni, On hereditary graph classes defined by forbidding Truemper configurations (PhD thesis, 2018) (standard reference, not scraped)