Pure pairs. IX. Transversal trees

Journal article

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.

Authors: Scott, A; Seymour, P; Spirkl, ST

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Society for Industrial and Applied Mathematics
• Journal: SIAM Journal on Discrete Mathematics
• Volume: 38
• Issue: 1
• Pages: 645-667
• Publication date: 2024-02-02
• Acceptance date: 2023-08-07
• DOI: 10.1137/21M1456509
• EISSN: 1095-7146
• ISSN: 0895-4801
• Language: English
• Keywords: FFR