Thomas's half-integral Erdős–Pósa conjecture for graph minors

Let HH be a graph. A graph GG half-integrally packs kk graphs if it contains subgraphs isomorphic to those graphs such that every vertex of GG belongs to at most two of the subgraphs. A graph GG contains HH as a minor if HH can be obtained from a subgraph of GG by vertex and edge contractions.

Thomas's conjecture. For every graph HH, there exists a function ff such that for every graph GG and every positive integer kk, either GG half-integrally packs kk graphs each containing HH as a minor, or there exists a set ZV(G)Z\subseteq V(G) with Zf(k)\lvert Z\rvert\leq f(k) such that GZG-Z does not contain HH as a minor.

This conjecture extends the Erdős–Pósa property for graph minors from integral to half-integral packing, potentially removing the planarity restriction on HH. The source presents it as a conjecture of Thomas; its resolution is not specified here.

Sources & referencesView supporting material

Primary source

Chun-Hung Liu, “Packing Topological Minors Half-Integrally”, arXiv:1707.07221 (2022).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.