Polynomial bound conjecture for excluding grasped clique minors
Polynomial bound conjecture for excluding grasped clique minors
Let and be polynomials. For integers , set
Let be a graph and let be an -wall in . A flat wall is a wall that is flat in the relevant surface decomposition, and a -central -decomposition is one satisfying the centrality condition defined for . Polynomial bound conjecture. There exist polynomials and such that either has a model of a minor grasped by , or there exist a set with , a surface of Euler genus at most , a -central -decomposition of of depth and breadth at most , and an -subwall of such that and is flat in .
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.