Skip to Main content Skip to Navigation
Journal articles

Bounded-degree graphs have arbitrarily large queue-number

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.
Document type :
Journal articles
Complete list of metadata

Cited literature [29 references]  Display  Hide  Download

https://hal.inria.fr/hal-00972310
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Submitted on : Thursday, April 3, 2014 - 4:07:50 PM
Last modification on : Monday, November 16, 2020 - 3:56:03 PM
Long-term archiving on: : Thursday, July 3, 2014 - 4:31:09 PM

File

541-2702-1-PB.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00972310, version 1

Collections

Citation

David R. Wood. Bounded-degree graphs have arbitrarily large queue-number. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2008, 10 (1), pp.27--34. ⟨hal-00972310⟩

Share

Metrics

Record views

114

Files downloads

951