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

About 9 years old · traced to

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 Z⊆V(G)Z\subseteq V(G) with ∣Z∣≤f(k)\lvert Z\rvert\leq f(k) such that G−ZG-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.

References

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.