Condensed-wall criterion for the edge-Erdős–Pósa property

About 8 years old · traced to

Let HH be a planar graph. An HH-expansion is a subdivision of HH, and a condensed wall is the graph class described in the paper. The edge-Erdős–Pósa property concerns the existence of bounded edge hitting sets for families of pairwise edge-disjoint subgraphs.

Condensed-wall conjecture. If there is an integer rr such that the condensed wall of size rr contains an HH-expansion, then the family of HH-expansions has the edge-Erdős–Pósa property.

The conjecture is motivated by the known positive cases for long cycles, theta-graphs, and K4K_4, each of which occurs as a minor in a sufficiently large condensed wall. The paper presents the condensed-wall containment condition as a proposed sufficient criterion, but does not prove it in general.

References

Primary source

Henning Bruhn, Matthias Heinlein and Felix Joos, “The edge-Erdős-Pósa property”, arXiv:1809.11038 (2018).

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.