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

Depends on

• A finite simple graph is a finite vertex set together with a set of two-element vertex subsets
• Subgraphs, induced subgraphs and spanning subgraphs
• Empty and complete graphs, complete bipartite graphs, and the convention that $P_n$ and $C_n$ have $n$ vertices
• The cardinality $\lvert A\rvert$ of a finite set
• $\lvert\mathcal{P}(A)\rvert = 2^{\lvert A\rvert}$ for finite $A$
• A subset of a finite set is finite, with $\lvert B\rvert \le \lvert A\rvert$, and equality holds if and only if $B = A$
• The well-ordering principle

Used by

• A c-sparse set X satisfies α(G[X])≥|X|/(c|X|+1), and a c-dense set satisfies ω(G[X])≥|X|/(c|X|+1) Corollary
• An α-narrow graph has a clique or stable set of size at least |V(G)|^1/(2α) Corollary
• Every bull-free graph has a clique or stable set of size at least |V(G)|^1/4 Corollary
• Every P₄-free graph has a clique or stable set of size at least the square root of its order Corollary
• Every perfect graph has a clique or stable set of size at least the square root of its order Corollary
• The five-cycle is bull-free but not perfect Counterexample
• A perfect graph Definition
• Generalized nice finite graph families Definition
• Homogeneous vertex sets and the homogeneous number hom(G)=max{ω(G),α(G)} Definition
• Perfect graphs Definition
• Property (*) for a finite graph family Definition
• The parameter kappa(G)=alpha(G)omega(G) Definition
• A two-block pure blockade can realize equality in the additive kappa theorem Example
• For 0≤ε<1/2, every sufficiently large ε-restricted set lies in one side Example
• In a disjoint union of cliques of order k the whole vertex set is (k/n)-sparse Example
• The 0-sparse sets are exactly the stable sets and the 0-dense sets exactly the cliques Example
• Every c-sparse set of size m contains a stable set of size at least m/2 False statement
• A complete connection of two perfect graphs is perfect Lemma
• A disjoint union of two perfect graphs is perfect Lemma
• A large Y-part in a structural comb partition yields the clique-or-stable-set outcome Lemma
• Complementation swaps cliques with stable sets, so ω(Ḡ)=α(G) Lemma
• hom(G[W])lehom(G) for every vertex subset W Lemma
• Without a large ε-sparse induced subgraph, the number of k-vertex stable sets is bounded Lemma
• Why this page says module where some sources say homogeneous set Remark
• A pure blockade with a cograph pattern has additive kappa Theorem
• A tau-critical graph has no wide pure blockade with cograph pattern Theorem
• A tau-critical graph with a large low-degree induced subgraph has a rooted stable-tooth comb Theorem
• 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 perfect graph satisfies |V(G)|<=kappa(G) Theorem
• The C5-free graphs satisfy a polynomial kappa bound Theorem
• The Erdos-Hajnal property is equivalent to the large-cograph, large-perfect, and kappa formulations Theorem

Dependency tree · two levels

29 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

• Reinhard Diestel, Graph Theory, Preview Chapter 1 (standard reference, not scraped)
• Valerio Boncompagni, On hereditary graph classes defined by forbidding Truemper configurations (PhD thesis, 2018) (standard reference, not scraped)