arXiv Analytics

Sign in

arXiv:2011.04195 [math.CO]AbstractReferencesReviewsResources

Stack-number is not bounded by queue-number

Vida Dujmović, David Eppstein, Robert Hickingbotham, Pat Morin, David R. Wood

Published 2020-11-09Version 1

We describe a family of graphs with queue-number at most 4 but unbounded stack-number. This resolves open problems of Heath, Leighton and Rosenberg (1992) and Blankenship and Oporowski (1999).

Categories: math.CO, cs.DM
Related articles:
arXiv:2108.09994 [math.CO] (Published 2021-08-23)
On the Queue-Number of Partial Orders
arXiv:2202.05327 [math.CO] (Published 2022-02-10)
Three-dimensional graph products with unbounded stack-number
arXiv:1806.04489 [math.CO] (Published 2018-06-12)
The queue-number of planar posets

Links

Toolbox