The genus conjecture for the prefix-reversal graph on four symbols

Let P4\mathbb{P}_4 be the prefix-reversal graph on the permutations of {1,2,3,4}\{1,2,3,4\}, and let γ(P4)\gamma(\mathbb{P}_4) denote its orientable genus. A graph is a pretzel graph if it admits the corresponding pretzel-graph embedding. Pretzel-graph conjecture. The graph P4\mathbb{P}_4 is a pretzel graph, and

γ(P4)=3.\gamma(\mathbb{P}_4)=3.

The authors report that the displayed rotation system has eight regions and indicate that this is likely the maximum number of regions obtainable from any rotation system, but they did not attempt all possible vertex labelings. Thus the claimed exact genus remains open in the supplied source.

Sources & referencesView supporting material

Primary source

Saúl A. Blanco and Charles Buehrle, “Bounds on the genus for 2-cell embeddings of prefix-reversal graphs”, arXiv:2306.11295 (2024).

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.