The planar-or-bounded-high-degree structure conjecture for graphs without a topological K_5

Let K5K_5 denote the complete graph on five vertices. A graph is a clique-sum of graphs G1,,GnG_1,\ldots,G_n if it is obtained by repeatedly gluing graphs along cliques. The degree of a vertex is its number of incident edges.

Planar-or-bounded-high-degree conjecture. There exist constants DD and aa such that every graph GG that does not contain K5K_5 as a topological minor can be expressed as a clique-sum of graphs G1,,GnG_1,\ldots,G_n such that, for each 1in1\leq i\leq n, either GiG_i is planar or GiG_i contains at most aa vertices of degree at least DD.

This conjecture would strengthen the preceding structure theorem by removing the vortices and apex vertices from its planar alternative. Its status is not resolved in the supplied source context.

Sources & referencesView supporting material

Primary source

Zdenek Dvorak, “A stronger structure theorem for excluded topological minors”, arXiv:1209.0129 (2012).

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.