Homogeneous vertex sets and the homogeneous number $\mathrm{hom}(G)=\max \{\omega (G),\alpha (G)\}$

Depends on

• Cliques, stable sets, the clique number $\omega(G)$ and stability number $\alpha(G)$

Used by

• Every perfect graph has a clique or stable set of size at least the square root of its order Corollary
• The polynomial Rödl property implies the Erdős–Hajnal property Corollary
• The (t,k)-homogeneous property Definition
• The Erdős–Hajnal property and an Erdős–Hajnal constant for a hereditary graph class Definition
• Every hereditary graph class of bounded order has the Erdős–Hajnal property Example
• For positive a,b, hom(K_a,b)=max{2,a,b} Example
• Kₙ and K̄ₙ both have homogeneous number n 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 self-complementary five-cycle satisfies hom(C₅)=2 Example
• A P₄-free graph on q vertices has a homogeneous set of size at least √q Lemma
• hom(G[W])lehom(G) for every vertex subset W 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
• Many good 2t-vertex subsets force many homogeneous k-sets Lemma
• The auxiliary pattern then has a polynomial-size clique or stable set Lemma
• Why this page says module where some sources say homogeneous set 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 H-free graph has a homogeneous set of size at least 2^c√log₂ n Theorem
• Every H-free graph has a homogeneous set of size at least 2^c√log₂ n log₂ log₂ n Theorem
• Every nonempty n-vertex graph satisfies hom(G)≥ 1/2 log₂ n Theorem
• Every P₃-free graph G satisfies hom(G)≥√|V(G)| Theorem
• For every n≥16 there is an n-vertex graph with hom(G)<3 log₂ n Theorem
• For every t≥1, the class of Kₜ-free graphs has 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

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)
• A. Chernikov, MATH 223M notes, sec. 3.1 (standard reference, not scraped)