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, B. Vogtenhuber

Research output: Chapter in Book/Report/Conference proceedingConference paperpeer-review


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 n2 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$. This shows that we have properly extended the class of drawings for which the Harary-Hill Conjecture is proved.
Original languageEnglish
Title of host publicationProc. XVII Encuentros de Geometría Computacional
Place of PublicationAlicante, Spain
Number of pages4
Publication statusPublished - 2017

Cite this