Edges between disjoint vertex sets; complete, anticomplete, pure and mixed pairs

Depends on

• A finite simple graph is a finite vertex set together with a set of two-element vertex subsets
• Adjacency, incidence, open and closed neighbourhoods, vertex degree, minimum degree and maximum degree

Used by

• Large almost-pure pair hypotheses yield a complete or anticomplete blockade Corollary
• The prime quotient produced by the modular decomposition of a connected and anticonnected graph has at least four vertices Corollary
• Mixedness of block pairs is not transitive Counterexample
• Omitting cross-block purity breaks the transversal conclusion Counterexample
• X can be c-sparse to Y while Y is not c-sparse to X Counterexample
• A rooted stable-tooth comb Definition
• Combs in a graph Definition
• Complete, anticomplete, pure, weakly sparse, and x-sparse blockades Definition
• Edge counts and densities between nonempty vertex sets Definition
• Modular partitions and the quotient graph they define Definition
• Modules of a graph, and the trivial modules Definition
• Sparsity of one vertex set to another, and weak sparsity of a pair Definition
• The mixed-block reachability relation on a blockade Definition
• The strong Erdős–Hajnal property for a hereditary graph class Definition
• Wonderful finite graph families Definition
• A large almost-pure pair extends an anticomplete blockade Example
• Complete and anticomplete disjoint pairs are 0-regular Example
• Complete, anticomplete and mixed vertex-set pairs in P₄ Example
• A complete-or-weakly-sparse blockade can be thinned to equal subblocks with directional sparsity Lemma
• A module of G[M] is a module of G whenever M is a module of G Lemma
• A polynomial homogeneous set in the auxiliary pattern yields a y⁴-restricted union Lemma
• A quotient block of connected or anticonnected blocks is again connected or anticonnected Lemma
• A separated anticonnected block pair forbids mixing in one direction Lemma
• A vertex mixed on a connected set has opposite adjacency on some edge of that set Lemma
• A vertex mixed on a quotient block but pure on each member block yields two mixed member blocks with opposite adjacency Lemma
• A vertex mixed on an anticonnected set yields opposite adjacency on a nonedge Lemma
• A vertex set is a module of G exactly when it is a module of Ḡ Lemma
• A wonderful anticonnected complete-or-sparse blockade yields a restricted subgraph or a large anticomplete pair Lemma
• Blocks from distinct mixed-block classes are pure to each other Lemma
• Distinct connected components are anticomplete, and distinct anticonnected components are complete Lemma
• Every union of connected components is a module, and so is every union of anticonnected components Lemma
• For a modular partition, a set of parts is a module of the quotient exactly when the union of those parts is a module of the graph Lemma
• For disjoint nonempty vertex sets, weak c-sparsity says exactly that the edge density is at most c Lemma
• If M is a module of G and W⊆ V(G), then M∩ W is a module of G[W] Lemma
• If two modules overlap, then each difference and their symmetric difference are modules Lemma
• In a connected and anticonnected graph, the union of two proper modules that meet is again a proper module Lemma
• In a connected graph, some vertex outside a nonempty proper module is complete to it Lemma
• In a special-vertex comb of a co-E-free graph, vertices in other comb blocks remain pure to every H₅-overlap quotient block Lemma
• In G₁ with G₂ substituted for a, the vertex set of G₂ is a module, the two factors are recovered as induced subgraphs, and substituting a one-vertex graph changes nothing Lemma
• Mixed anticonnected blocks lift pattern obstructions to the ambient graph Lemma

…and 20 more results.

Dependency tree · two levels

3 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)