Graphs with queue number three and unbounded stack number

Abstract

We prove that the graphs $T\boxslash P$ have unbounded stack number and queue number $3$, where $T$ is a tree and $P$ is a path, and $\boxslash$ denotes the graph strong product but with one of the directions removed. The previous best known results is that graphs with queue number $4$ can have unbounded stack number.

arXiv comment31 pages, 7 figures