Stack and queue numbers of graphs revisited

HLINĚNÝ, Petr a Adam STRAKA. Stack and queue numbers of graphs revisited. EUROPEAN JOURNAL OF COMBINATORICS. ENGLAND: ACADEMIC PRESS LTD- ELSEVIER SCIENCE LTD, 2025, roč. 129, č. 1, s. 104094-104099. ISSN 0195-6698. Dostupné z: https://doi.org/10.1016/j.ejc.2024.104094.

Základní údaje

Originální název

Stack and queue numbers of graphs revisited

Autoři

HLINĚNÝ, Petr ORCID a Adam STRAKA

Vydání

EUROPEAN JOURNAL OF COMBINATORICS, ENGLAND, ACADEMIC PRESS LTD- ELSEVIER SCIENCE LTD, 2025, 0195-6698

---

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Nizozemské království

Utajení

není předmětem státního či obchodního tajemství

Odkazy

arXiv preprint

Impakt faktor

Impact factor: 0.900 v roce 2024

Označené pro přenos do RIV

Ano

Organizační jednotka

Fakulta informatiky

DOI

https://doi.org/10.1016/j.ejc.2024.104094

UT WoS

001534964300001

EID Scopus

2-s2.0-85211225425

Klíčová slova anglicky

stack number; queue number; Cartesian product

Příznaky

Mezinárodní význam, Recenzováno

---

Anotace

V originále

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 partially 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.