Bounded-degree graphs have arbitrarily large queue-number

David R. Wood

doi:10.46298/dmtcs.434

David R. Wood - Bounded-degree graphs have arbitrarily large queue-number

dmtcs:434 - Discrete Mathematics & Theoretical Computer Science, January 1, 2008, Vol. 10 no. 1 - https://doi.org/10.46298/dmtcs.434

Bounded-degree graphs have arbitrarily large queue-number

Authors: David R. Wood ¹

1 Departament de Matemàtica Aplicada II

It is proved that there exist graphs of bounded degree with arbitrarily large queue-number. In particular, for all \Delta ≥ 3 and for all sufﬁciently large n, there is a simple \Delta-regular n-vertex graph with queue-number at least c√\Delta_n^{1/2-1/\Delta} for some absolute constant c.

https://doi.org/10.46298/dmtcs.434

Source: HAL:hal-00972310v1

Volume: Vol. 10 no. 1

Section: Graph and Algorithms

Published on: January 1, 2008

Imported on: March 26, 2015

Keywords: [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

Linked publications - datasets - softwares

Source : ScholeXplorer IsRelatedTo ARXIV 2011.04195 Source : ScholeXplorer IsRelatedTo DOI 10.1007/s00493-021-4585-7 Source : ScholeXplorer IsRelatedTo DOI 10.48550/arxiv.2011.04195 10.48550/arxiv.2011.04195 10.1007/s00493-021-4585-7 10.1007/s00493-021-4585-7 2011.04195 Stack-Number is Not Bounded by Queue-Number

David R. Wood - Bounded-degree graphs have arbitrarily large queue-number

Linked publications - datasets - softwares

2 Documents citing this article

Share and export

Consultation statistics