Stack and Queue Numbers of Graphs Revisited

Varování

Publikace nespadá pod Ekonomicko-správní fakultu, ale pod Fakultu informatiky. Oficiální stránka publikace je na webu muni.cz.
Autoři

HLINĚNÝ Petr STRAKA Adam

Rok publikování 2023
Druh Článek ve sborníku
Konference European Conference on Combinatorics, Graph Theory and Applications EUROCOMB’23
Fakulta / Pracoviště MU

Fakulta informatiky

Citace
Doi http://dx.doi.org/10.5817/CZ.MUNI.EUROCOMB23-083
Klíčová slova linear layout; stack number; queue number
Popis 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.
Související projekty:

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.