HLINĚNÝ, Petr and Adam STRAKA. Stack and Queue Numbers of Graphs Revisited. Online. In European Conference on Combinatorics, Graph Theory and Applications EUROCOMB’23. Brno, Czech Republic: MUNI Press, 2023, p. 601-606. ISSN 2788-3116. Available from: https://dx.doi.org/10.5817/CZ.MUNI.EUROCOMB23-083.
Other formats:   BibTeX LaTeX RIS
Basic information
Original name Stack and Queue Numbers of Graphs Revisited
Authors HLINĚNÝ, Petr (203 Czech Republic, guarantor, belonging to the institution) and Adam STRAKA (703 Slovakia, belonging to the institution).
Edition Brno, Czech Republic, European Conference on Combinatorics, Graph Theory and Applications EUROCOMB’23, p. 601-606, 6 pp. 2023.
Publisher MUNI Press
Other information
Original language English
Type of outcome Proceedings paper
Field of Study 10201 Computer sciences, information science, bioinformatics
Country of publisher Czech Republic
Confidentiality degree is not subject to a state or trade secret
Publication form electronic version available online
RIV identification code RIV/00216224:14330/23:00131121
Organization unit Faculty of Informatics
ISSN 2788-3116
Doi http://dx.doi.org/10.5817/CZ.MUNI.EUROCOMB23-083
Keywords in English linear layout; stack number; queue number
Tags formela-conference
Tags International impact, Reviewed
Changed by Changed by: prof. RNDr. Petr Hliněný, Ph.D., učo 168881. Changed: 22/3/2024 07:59.
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.
Links
MUNI/A/1081/2022, interní kód MUName: Modelování, analýza a verifikace (2023)
Investor: Masaryk University
PrintDisplayed: 15/6/2024 13:45