Edge-EP property for planar J-expansions

Open Problem (edge-EP property characterization for planar graph expansions) · arXiv:1912.07965

arXiv Problem medium confidence— first stated 2020-06-08

Authors: Wouter Cames van Batenburg, Gwenaël Joret, Arthur Ulmer

Status open high confidence

The characterization of which planar graphs J yield the edge-Erdős-Pósa property for J-expansions remains open. Partial progress has been made for the specific family of ladders: Steck and Ulmer (2024) showed that ladders with 3 rungs (and the house graph) have the edge-EP property while ladders with 14 or more rungs do not, narrowing the gap but leaving the full characterization of intermediate cases open. No complete characterization has been established, and the condensed wall has been proposed as a key structural candidate for such a characterization.

Cited literature (1)

partial On the Edge-Erdős–Pósa Property of Ladders (2024)

Raphael Steck, Arthur Ulmer · Graphs and Combinatorics · arXiv:2003.03236 · doi:10.1007/s00373-024-02765-w

Shows that ladders with 3 rungs and the house graph have the edge-EP property while ladders with 14 or more rungs do not, contributing partial progress toward the open characterization problem for planar J.

Reviewer notes. The full characterization of planar graphs J for which J-expansions have the edge-EP property remains open. The condensed wall has been proposed as a key structural tool, and a conjecture by Bruhn, Heinlein, and Joos suggests that if a planar graph H is a minor of the condensed wall of some size r, then H has the edge-EP property. The ladder case (arXiv:2003.03236) is the most directly relevant follow-up found, making partial progress on a specific subfamily.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Problem. Finding a characterization for the planar graphs $J$ such that $J$-expansions have the edge-Erd\H{o}s-P\'osa property remains an intriguing open problem.

Context

Robertson and Seymour showed that $J$-expansions have the vertex-EP property if and only if $J$ is planar. By contrast, it was shown in [4] that there exist planar graphs $J$ — in particular sufficiently large ladders and subcubic trees with sufficiently large pathwidth — for which $J$-expansions do not have the edge-EP property. The precise characterization of which planar $J$ yield the edge-EP property is unknown.

Notes. Stated in prose in the introduction as 'an intriguing open problem'; no labelled theorem environment. Section 5, which the paper explicitly announces contains further open problems, appears to be missing from the PDF extraction — additional items likely exist there.

Source paper

Erdős-Pósa from ball packing
Wouter Cames van Batenburg, Gwenaël Joret, Arthur Ulmer · 2020-06-08
https://arxiv.org/abs/1912.07965 PDF source