Packing topological minors half‐integrally
Chun‐Hung Liu
Abstract
The packing problem and the covering problem are two of the most general questions in graph theory. The Erdős–Pósa property characterizes the cases when the optimal solutions of these two problems are bounded by functions of each other. Robertson and Seymour proved that when packing and covering H $H$ -minors for any fixed graph H $H$ , the planarity of H $H$ is equivalent to the Erdős–Pósa property. Thomas conjectured that the planarity is no longer required if the solution of the packing problem is allowed to be half-integral. In this paper, we prove that this half-integral version of Erdős–Pósa property holds for packing and covering H $H$ -topological minors, for any fixed graph H $H$ , which easily implies Thomas' conjecture. In fact, we prove an even stronger statement in which those topological minors are rooted at any choice of prescribed subsets of vertices. A number of results on H $H$ -topological minor-free or H $H$ -minor-free graphs have conclusions or requirements tied to properties of H $H$ . Classes of graphs that can half-integrally pack only a bounded number of H $H$ -topological minors or H $H$ -minors are more general topological minor-closed or minor-closed families whose minimal obstructions are more complicated than H $H$ . Our theorem provides a general machinery to extend those results to those more general classes of graphs without losing their tight connections to H $H$ .