Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. Bounded-degree graph ...
Article

Bounded-degree graphs have arbitrarily large queue-number

David R. Wood ORCID (1)
(1) Departament de Matemàtica Aplicada II
Download article
Open on HAL
Imported on
March 26, 2015
Published on
January 1, 2008
Last modified on
March 31, 2025
Volume 10
vol. 10:1
Graph and Algorithms
DOI
10.46298/dmtcs.434
License
https://about.hal.science/hal-authorisation-v1
Indicators
930
Views
822
Downloads

Bounded-degree graphs have arbitrarily large queue-number

David R. Wood ORCID (1)
(1) Departament de Matemàtica Aplicada II
Abstract
It is proved that there exist graphs of bounded degree with arbitrarily large queue-number. In particular, for all \Delta ≥ 3 and for all sufficiently 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.
Keywords
  • [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
Cited by

Source: OpenCitations

  • Planar graphs of bounded degree have bounded queue number

    Kölner Universitäts PublikationsServer (Universität zu Köln)

    Authors : Michael Bekos ORCID, Henry Förster ORCID, Martin Gronemann ORCID, Tamara Mchedlidze ORCID, Fabrizio Montecchiani ORCID, Chrysanthi Raftopoulou ORCID, Torsten Ueckerdt ORCID

    Journal reference : Volume , 2019, pp. 176-184

    DOI : 10.1145/3313276.3316324

  • Drawing graphs on few lines and few planes

    DOAJ (DOAJ: Directory of Open Access Journals)

    Authors : Steven Chaplick ORCID, Krzysztof Fleszar ORCID, Fabian Lipp ORCID, Alexander Ravsky, Oleg Verbitsky ORCID, Alexander Wolff ORCID

    Journal reference : Volume , 2020, pp.

    DOI : 10.20382/jocg.v11i1a17

  • Notes on Graph Product Structure Theory

    arXiv (Cornell University)

    Authors : Zdeněk Dvořák, Tony Huynh, Gwenael Joret, Chun-Hung Liu, David R. Wood

    Journal reference : Volume , 2021, pp. 513-533

    DOI : 10.1007/978-3-030-62497-2_32
Preview
Loading PDF preview...