Stack and Queue Numbers of Graphs Revisited

Warning

This publication doesn't include Faculty of Economics and Administration. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

HLINĚNÝ Petr STRAKA Adam

Year of publication 2023
Type Article in Proceedings
Conference European Conference on Combinatorics, Graph Theory and Applications EUROCOMB’23
MU Faculty or unit

Faculty of Informatics

Citation
Doi http://dx.doi.org/10.5817/CZ.MUNI.EUROCOMB23-083
Keywords linear layout; stack number; queue number
Description 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.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.