The Kn+5K_{n+5} and K32,1nK_{3^2,1^n} families conjecture for nn-apex obstructions

A graph is nn-apex if deleting nn or fewer vertices results in a planar graph. A graph is a minor of another graph if it can be obtained by contracting edges in a subgraph. Let On\mathcal{O}_n be the set of graphs that are not nn-apex although every proper minor is. The Kn+5K_{n+5} and K32,1nK_{3^2,1^n} families conjecture. For each n>0n>0, the Kn+5K_{n+5} and K32,1nK_{3^2,1^n} families are in On\mathcal{O}_n. Here Kn+5K_{n+5} is the complete graph on n+5n+5 vertices, K32,1nK_{3^2,1^n} is the complete multipartite graph with two parts of three vertices and a further nn singleton parts, and each family consists of graphs obtained through zero or more triangle-Y or Y-triangle moves. The conjecture would identify these families as minor-minimal obstructions to the nn-apex property and provides evidence toward determining the finite obstruction sets On\mathcal{O}_n; the paper reports computational evidence but does not establish the claim in general.

Sources & referencesView supporting material

Primary source

Thomas W. Mattman and Mike Pierce, “The K_n+5 and K_3^2,1^n families are obstructions to n-apex”, arXiv:1603.00885 (2016).

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.