Polynomial bound conjecture for excluding grasped clique minors

Let ff and gg be polynomials. For integers r,p0r,p\geq 0, set

R=f(r,p)+g(p).R=f(r,p)+g(p).

Let GG be a graph and let WW be an RR-wall in GG. A flat wall is a wall that is flat in the relevant surface decomposition, and a WW-central a3a3-decomposition is one satisfying the centrality condition defined for WW. Polynomial bound conjecture. There exist polynomials ff and gg such that either GG has a model of a KpK_p minor grasped by WW, or there exist a set AV(G)A\subseteq V(G) with Ag(p)|A|\leq g(p), a surface Σ\Sigma of Euler genus at most g(p)g(p), a WW-central Σ\Sigma-decomposition δ\delta of GAG-A of depth and breadth at most g(p)g(p), and an rr-subwall WW' of WW such that V(W)A=V(W')\cap A=\emptyset and WW' is flat in δ\delta.

The conjecture proposes replacing the exponential dependence in the theorem's current bound by polynomial functions. It concerns the quantitative structure available when a graph does not contain a clique minor grasped by a sufficiently large wall; the theorem preceding it establishes the corresponding alternative with an exponential bound.

Sources & referencesView supporting material

Primary source

Ken-ichi Kawarabayashi, Robin Thomas and Paul Wollan, “Quickly excluding a non-planar graph”, arXiv:2010.12397 (2021).

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.