Stack and Queue Numbers of Graphs Revisited
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909392917495808 |
|---|---|
| author | Hliněný, Petr Straka, Adam |
| author_facet | Hliněný, Petr Straka, Adam |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2303_10116 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Stack and Queue Numbers of Graphs Revisited Hliněný, Petr Straka, Adam Combinatorics Discrete Mathematics 68R10 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. |
| title | Stack and Queue Numbers of Graphs Revisited |
| topic | Combinatorics Discrete Mathematics 68R10 |
| url | https://arxiv.org/abs/2303.10116 |