The Erdős–Hajnal property and an Erdős–Hajnal constant for a hereditary graph class

Depends on

• Homogeneous vertex sets and the homogeneous number $\operatorname{hom}(G)=\max\{\omega(G),\alpha(G)\}$
• Hereditary graph classes
• Real powers for positive bases, with the zero-base positive-exponent convention

Used by

• Every bull-free graph has a clique or stable set of size at least |V(G)|^1/4 Corollary
• Every graph has the Erdős–Hajnal property if and only if every prime graph does Corollary
• Every graph on at most three vertices has the Erdős–Hajnal property Corollary
• For a single graph, the Erdős–Hajnal property, the polynomial Rödl property, and virality are equivalent Corollary
• Substituting a complete or an edgeless graph for a vertex preserves the Erdős–Hajnal property Corollary
• The bull graph has the Erdős-Hajnal property Corollary
• The four-vertex path has the Erdős-Hajnal property Corollary
• The hereditary class of all finite graphs does not have the Erdős–Hajnal property Corollary
• The polynomial Rödl property implies the Erdős–Hajnal property Corollary
• The singleton Bird family has property (*) Corollary
• Leaf-reducible finite graph families Definition
• The structural comb-partition hypothesis Definition
• Every hereditary graph class of bounded order has the Erdős–Hajnal property Example
• Substituting an edge for an endpoint of P₃ gives a four-vertex graph with the Erdős–Hajnal property Example
• The Bird theorem reaches an induced bull witness Example
• The classes of complete graphs and of empty graphs have Erdős–Hajnal constant 1 Example
• The E theorem reaches an induced P₅ witness Example
• The five-vertex path is leaf-reducible Example
• A large Y-part in a structural comb partition yields the clique-or-stable-set outcome Lemma
• A wide integral geometric layer forces the complete-or-anticomplete property-(*) blockade Lemma
• Every smaller positive exponent is again an Erdős–Hajnal constant 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
• The auxiliary pattern then has a polynomial-size clique or stable set Lemma
• The E-graph and Bird singleton families are leaf-reducible Lemma
• The family consisting of H₅ and co-E has the Erdős–Hajnal property Lemma
• A hereditary class has the Erdős–Hajnal property exactly when its complementary class does, with the same constants Proposition
• The Erdős–Hajnal property and each of its constants pass to hereditary subclasses Proposition
• The Erdős–Hajnal conjecture: every fixed forbidden induced graph admits a positive exponent Remark
• The perfect-induced-subgraph formulation of the Erdos-Hajnal conjecture Remark
• Alon–Pach–Solymosi: if H₁ and H₂ have the Erdős–Hajnal property, so does the graph obtained from H₁ by substituting H₂ for a vertex Theorem
• Every finite family with the Erdős–Hajnal property is viral Theorem
• Every P₃-free graph G satisfies hom(G)≥√|V(G)| Theorem
• For a finite family, the Erdős–Hajnal property, the polynomial Rödl property, and virality are equivalent Theorem
• For every t≥1, the class of Kₜ-free graphs has the Erdős–Hajnal property Theorem
• Leaf-reducible wonderful generalized nice finite families have the Erdős-Hajnal property Theorem
• The Bird graph has the Erdős-Hajnal property Theorem
• The E-graph has the Erdős-Hajnal property Theorem
• The Erdos-Hajnal property is equivalent to the large-cograph, large-perfect, and kappa formulations Theorem
• The single-forbidden-graph and finite-nonempty-family formulations of the Erdős–Hajnal conjecture are equivalent Theorem
• The special-vertex-local structural-partition criterion implies property (*) Theorem

…and 1 more result.

Dependency tree · two levels

8 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

• M. Chudnovsky, The Erdos-Hajnal Conjecture: A Survey, sec. 1 (standard reference, not scraped)
• Erdős-Hajnal beyond the five-vertex path (standard reference, not scraped)