Abstract
Fix k > 0, and let G be a graph, with vertex set partitioned into k subsets (``blocks"") of approximately equal size. An induced subgraph of G is ``transversal"" (with respect to this partition) if it has exactly one vertex in each block (and therefore it has exactly k vertices). A ``pure pair"" in G is a pair X, Y of disjoint subsets of V (G) such that either all edges between X, Y are present or none are; and in the present context we are interested in pure pairs (X, Y ) where each of X, Y is a subset of one of the blocks, and not the same block. This paper collects several results and open questions concerning how large a pure pair must be present if various types of transversal subgraphs are excluded.
| Original language | American English |
|---|---|
| Pages (from-to) | 645-667 |
| Number of pages | 23 |
| Journal | SIAM Journal on Discrete Mathematics |
| Volume | 38 |
| Issue number | 1 |
| DOIs | |
| State | Published - 2024 |
ASJC Scopus subject areas
- General Mathematics
Keywords
- induced subgraphs
- pure pairs
- trees