Agile Sets in Graphs

Abstract

A set of vertices in a graph is agile if, however we partition the set into two parts, we can always find two vertex-disjoint connected subgraphs where one covers the first and the other the second part. We present a characterization for the existence of large agile sets in terms of $K_{2,k}$ and large strip minors.

20 pages, 3 figures

References in corpus (1)

• A generalization of the Grid Theorem