Vertex-minimal maximum-excess triangulation conjecture
Let be a surface, let be the largest integer such that embeds in , and call a triangulation vertex-minimal if it has the minimum number of vertices among triangulations of . An irreducible triangulation is a triangulation with no contractible edge, and the excess is the quantity defined in the paper.
Vertex-minimality conjecture. For every surface , the maximum excess is attained by some vertex-minimal triangulation of that contains as a subgraph. Moreover, if
then every irreducible triangulation with maximum excess is vertex-minimal and contains as a subgraph.
The source gives the vertex orders of vertex-minimal triangulations and presents this as a final strengthening of the preceding complete-subgraph conjecture. Its general validity remains open.
References
Primary source
Vida Dujmović, Gašper Fijavž, Gwenaël Joret, Thom Sulanke and David R. Wood, “The maximum number of cliques in a graph embedded in a surface”, arXiv:0906.4142 (2011).
Additional references
2 papers in this index state this conjecture (2003–2009). The statement above is taken from the most recent of them; the others are arXiv:math/0311116.
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
No solutions have been posted yet.