Complete, anticomplete, pure, weakly sparse, and $x$-sparse blockades

Depends on

• Blockades, their length, their width, and their support
• Sparsity of one vertex set to another, and weak sparsity of a pair
• Edges between disjoint vertex sets; complete, anticomplete, pure and mixed pairs

Used by

• Property (*) for a finite graph family Definition
• Qid restricted blockade with empty blocks Definition
• Quantitative divisiveness for a finite forbidden family Definition
• Sparse orientations of a blockade Definition
• The pattern graph of a pure blockade Definition
• The structural comb-partition hypothesis Definition
• A complete four-blockade gives a four-vertex clique Example
• A pure blockade that is neither complete nor anticomplete Example
• An upside-down comb with anticonnected blocks creates a P₅ Example
• FALSE: every pure blockade is either complete or anticomplete False statement
• FALSE: reversing the order of the blocks never changes x-sparsity False statement
• A hatted-five-cycle-free rooted stable-tooth comb yields a large pure blockade of components Lemma
• A maximal pure blockade with large total a-mass must already have at least ε⁻² blocks Lemma
• A semisparse blockade can be sampled to anticonnected blocks with nearly pure relations Lemma
• A sparse host has many leaf extensions, few smaller copies, or a long sparse blockade Lemma
• A sparse P₅-free graph either sparsifies further or yields a pure blockade or a large sparse pair Lemma
• A sparse P₅-free graph yields a complete or anticomplete blockade or a sparser subgraph Lemma
• A sparse P₅-free graph yields deeper sparsification or a complete blockade or a large anticomplete set Lemma
• A transversal of wide structural blocks yields the pure blockade outcome Lemma
• Anticonnected block contraction turns an upside-down comb into a pure blockade Lemma
• Homogeneous sets in pure-blockade patterns lift to complete or anticomplete blockades Lemma
• Quantitatively divisive finite families are viral Lemma
• Refining the largest layout block forces local blockade length at least ε⁻¹ Lemma
• A long blockade without a large pure pair contains a rainbow forest or its complement Theorem
• A long blockade yields a wide cograph-pattern subblockade or a rainbow forest Theorem
• A pure blockade with a perfect pattern has a large complete or anticomplete subblockade Theorem
• A tau-critical graph has no wide pure blockade with cograph pattern Theorem
• Complete or anticomplete blockade hypotheses force an ε-restricted induced subgraph Theorem
• Local pure or x-sparse blockades yield a nice blockade Theorem
• P₅-free graphs admit a pure or x-sparse polynomial blockade Theorem
• The special-vertex-local structural-partition criterion implies property (*) Theorem

Dependency tree · two levels

7 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

• Tung Nguyen, Alex Scott, and Paul Seymour, Induced subgraph density. VII. The five-vertex path (standard reference, not scraped)
• Shenwei Huang, Yiao Ju, and Yidong Zhou, Erdős-Hajnal beyond the five-vertex path (standard reference, not scraped)