## 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 | English (US) |
---|---|

Pages (from-to) | 645-667 |

Number of pages | 23 |

Journal | SIAM Journal on Discrete Mathematics |

Volume | 38 |

Issue number | 1 |

DOIs | |

State | Published - 2024 |

## All Science Journal Classification (ASJC) codes

- General Mathematics

## Keywords

- induced subgraphs
- pure pairs
- trees