Linear xc bound for bounded-genus spanning trees

Conjecture 1 · arXiv:1604.07976

arXiv Conjecture high confidence— first stated 2017-01-09

Authors: Samuel Fiorini, Tony Huynh, Gwenaël Joret, Kanstantsin Pashkovich

Status open high confidence

Conjecture 1 from arXiv:1604.07976 — that xc(P_{sp.trees}(G)) = O(|V|) for any connected graph G embedded in a fixed surface — remains open as of 2026. The best known upper bound for fixed-genus graphs is still O(n^{3/2}) (the bound from the source paper). A 2021 follow-up by Aprile, Fiorini, Huynh, Joret, and Wood (arXiv:2106.11945) extends the O(n^{3/2}) result to all proper minor-closed classes and beyond, but does not improve the exponent for surface-embedded graphs or establish the conjectured linear bound.

Cited literature (1)

partial Smaller extended formulations for spanning tree polytopes in minor-closed classes and beyond (2021)

Manuel Aprile, Samuel Fiorini, Tony Huynh, Gwenaël Joret, David R. Wood · Electronic Journal of Combinatorics · arXiv:2106.11945

Proves xc(P_{sp.trees}(G)) = O(n^{3/2}) for connected n-vertex graphs in any proper minor-closed class, extending the O(n^{3/2}) bound of the source paper beyond genus-bounded graphs, but leaving the conjectured O(|V|) bound for fixed-surface graphs unresolved.

Reviewer notes. The O(n) bound is known for planar graphs (Williams 2002) and is the conjectured bound for all fixed-genus surfaces. The 2021 paper arXiv:2106.11945 (published in EJC v28i4p47) is the only identified follow-up; it broadens the O(n^{3/2}) result but does not break the exponent barrier for surface-embedded graphs. Tony Huynh's paper list (verified via WebFetch) confirms no further paper resolving this conjecture.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Conjecture. If $G = (V, E)$ is a connected graph embedded in a fixed surface, then $\mathrm{xc}(P_{\mathrm{sp.trees}}(G)) = O(|V|)$.

Context

The authors prove an $O(g^{1/2}|V|^{3/2} + g^{3/2}|V|^{1/2})$ upper bound for graphs embedded in a surface of genus $g$ (Theorem 3). They conjecture that this can be improved to match the linear bound known for planar graphs (Theorem 2, due to Williams).

Source paper

Smaller Extended Formulations for the Spanning Tree Polytope of Bounded-genus Graphs
Samuel Fiorini, Tony Huynh, Gwenaël Joret, Kanstantsin Pashkovich · 2017-01-09
https://arxiv.org/abs/1604.07976 PDF source