The and families conjecture for -apex obstructions
The and families conjecture for -apex obstructions
A graph is -apex if deleting 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 be the set of graphs that are not -apex although every proper minor is. The and families conjecture. For each , the and families are in . Here is the complete graph on vertices, is the complete multipartite graph with two parts of three vertices and a further 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 -apex property and provides evidence toward determining the finite obstruction sets ; 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
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.