Bishellable drawings of $K_n$

B. M. Ábrego, O. Aichholzer, S. Fernández-Merchant, D. McQuillan, B. Mohar, P. Mutzel, P. Ramos, R. B. Richter, and B. Vogtenhuber

Abstract:

In this work, we generalize the concept of $s$-shellability to bishellability, where the former implies the latter in the sense that every $s$-shellable drawing is, for any $b \leq s-2$, also $b$-bishellable. Our main result is that $(\lfloor \frac{n}{2} \rfloor\!-\!2)$-bishellability also guarantees, with a simpler proof than for $s$-shellability, that a drawing has at least $H(n)$ crossings. We exhibit a drawing of $K_{11}$ that has $H(11)$ crossings, is 3-bishellable, and is not $s$-shellable for any $s\geq5$. This shows that we have properly extended the class of drawings for which the Harary-Hill Conjecture is proved.

Reference: B. M. Ábrego, O. Aichholzer, S. Fernández-Merchant, D. McQuillan, B. Mohar, P. Mutzel, P. Ramos, R. B. Richter, and B. Vogtenhuber. Bishellable drawings of $k_n$. In Proc. XVII Encuentros de Geometría Computacional, pages 17-20, Alicante, Spain, 2017.