Vertex-minimal maximum-excess triangulation conjecture

About 23 years old · traced to

Let Σ\Sigma be a surface, let ω\omega be the largest integer such that KωK_\omega embeds in Σ\Sigma, and call a triangulation vertex-minimal if it has the minimum number of vertices among triangulations of Σ\Sigma. 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 Σ\Sigma, the maximum excess is attained by some vertex-minimal triangulation of Σ\Sigma that contains KωK_\omega as a subgraph. Moreover, if

Σ∉{N2,N3},\Sigma\notin\{\mathbb{N}_2,\mathbb{N}_3\},

then every irreducible triangulation with maximum excess is vertex-minimal and contains KωK_\omega 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

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.