Stack and Queue Numbers of Graphs Revisited

EUROCOMB’23

Abstract
A long-standing question of the mutual relation between the stack and queue numbers of a graph, explicitly emphasized by Dujmović and Wood in 2005, was ``half-answered‘‘ by Dujmović, Eppstein, Hickingbotham, Morin and Wood in 2022; they proved the existence of a graph family with the queue number at most $4$ but unbounded stack number. We give an alternative very short, and still elementary, proof of the same fact.

Pages:
601–606
References

Gail Adele Atneosen. On the embeddability of compacta in n-books: intrinsic and extrinsic properties. Michigan State University, 1968.

Vida Dujmović, David Eppstein, Robert Hickingbotham, Pat Morin, and David R. Wood. Stack-number is not bounded by queue-number. Combinatorica, 42(2):151-164, 2022.
https://doi.org/10.1007/s00493-021-4585-7

Vida Dujmović and David R Wood. Stacks, queues and tracks: Layouts of graph subdivisions. Discrete Mathematics and Theoretical Computer Science, 7:155-202, 2005.
https://doi.org/10.46298/dmtcs.346

Pál Erdös and G. Szekeres. A combinatorial problem in geometry. Compositio Mathematica, 2:463-470, 1935.

David Gale. The game of hex and the Brouwer fixed-point theorem. The American Mathematical Monthly, 86(10):818-827, 1979.
https://doi.org/10.1080/00029890.1979.11994922

Lenwood S. Heath, Frank Thomson Leighton, and Arnold L. Rosenberg. Comparing queues and stacks as machines for laying out graphs. SIAM Journal on Discrete Mathematics, 5(3):398-412, 1992.
https://doi.org/10.1137/0405031

Lenwood S. Heath and Arnold L. Rosenberg. Laying out graphs using queues. SIAM Journal on Computing, 21(5):927-958, 1992.
https://doi.org/10.1137/0221055

C.A. Persinger. Subsets of n-books in E3. Pacific Journal of Mathematics, 18(1):169-173, 1966.
https://doi.org/10.2140/pjm.1966.18.169

F. P. Ramsey. On a problem of formal logic. Proceedings of the London Mathematical Society, 30(1):264-286, 1930.
https://doi.org/10.1112/plms/s2-30.1.264

Adam Straka. Stack number and queue number of graphs, 2023. Bachelor's thesis, Masaryk University, Faculty of Informatics. URL: https://is.muni.cz/th/m5pwj/.

Adam Straka. Stack number and queue number of graphs, 2023. arXiv:2305.09700.

David R Wood. Queue layouts of graph products and powers. Discrete Mathematics & Theoretical Computer Science, 7, 2005.
https://doi.org/10.46298/dmtcs.352

Metrics

0

Views

0

PDF views