Packing Topological Minors Half-Integrally

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$-minors for any fixed graph $H$, the planarity of $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$-topological minors, for any fixed graph $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$-topological minor free or $H$-minor free graphs have conclusions or requirements tied to properties of $H$. Classes of graphs that can half-integrally pack only a bounded number of $H$-topological minors or $H$-minors are more general topological minor-closed or minor-closed families whose minimal obstructions are more complicated than $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$.

References in corpus (4)

• Planar graphs have bounded queue-number
• Sparse universal graphs for planarity
• Clustered Variants of Hajós' Conjecture
• A stronger structure theorem for excluded topological minors

Cited by in corpus (3)

• A unified half-integral Erdős-Pósa theorem for cycles in graphs labelled by multiple abelian groups
• A global decomposition theorem for excluding immersions in graphs with no edge-cut of order three
• Packing A-Paths of Length Zero Modulo Four