Stack and Queue Numbers of Graphs Revisited

• 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
• 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

• Modelování, analýza a verifikace (2023)