Linear extension complexity conjecture for spanning tree polytopes of proper minor-closed graph families
Linear extension complexity conjecture for spanning tree polytopes of proper minor-closed graph families
Let be a proper minor-closed family of graphs, and let be a connected graph in . Let denote the convex hull of the characteristic vectors of the spanning trees of . The minor-closed spanning tree polytope conjecture.
This would extend the proposed linear bound from fixed-surface graph families to all proper minor-closed families. The source presents it as a further possible generalization, and it remains open.
Sources & referencesView supporting material
Primary source
Samuel Fiorini, Tony Huynh, Gwenaël Joret and Kanstantsin Pashkovich, “Smaller Extended Formulations for the Spanning Tree Polytope of Bounded-genus Graphs”, arXiv:1604.07976 (2017).
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.