Stack-number is not bounded by queue-number
arXiv:2011.04195 · doi:10.1007/s00493-021-4585-7
Abstract
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).
References in corpus (6)
- Layout of Graphs with Bounded Tree-Width
- Characterisations and Examples of Graph Classes with Bounded Expansion
- Graph Treewidth and Geometric Thickness Parameters
- Layered Separators in Minor-Closed Graph Classes with Applications
- Book Embeddings of Graph Products
- Graph product structure for non-minor-closed classes