Stack-number is not bounded by queue-number.
V. Dujmović,
D. Eppstein,
R. Robert Hickingbotham,
P. Morin, and
D. R. Wood.
arXiv:2011.04195.
Combinatorica 42: 151–164, 2022, doi:10.1007/s00493-021-4585-7.
Stack number is also known as page number or book thickness; it is the minimum number of stacks needed so that you can process the vertices of a graph in some sequence, pushing each edge onto one of the stacks when you process its first endpoint and popping it from the same stack when you process its second endpoint. Queue number is defined in the same way using queues instead of stacks. We show that the strong products of triangular grids and high-degree stars have bounded queue number but unbounded stack number. This result disproves the Blankenship–Oporowski conjecture, according to which subdividing edges of a graph a constant number of times cannot decrease its stack number from non-constant to constant, because subdivisions of the same products also have bounded stack number. It also confirms a conjecture of Bonnet et al on the existence of graphs with bounded sparse twin-width and unbounded stack number.