Bounded-Degree Graphs have Arbitrarily Large Queue-Number

Simple item page
dc.creatorWood, David R.
dc.date2006-01-12
dc.date2006-02-20
dc.date.accessioned2026-07-07T10:01:29Z
dc.date.available2026-07-07T10:01:29Z
dc.descriptionIt is proved that there exist graphs of bounded degree with arbitrarily large queue-number. In particular, for all $Δ\geq3$ and for all sufficiently large $n$, there is a simple $Δ$-regular $n$-vertex graph with queue-number at least $c\sqrtΔn^{1/2-1/Δ}$ for some absolute constant $c$.
dc.identifierhttps://arxiv.org/abs/math/0601293
dc.identifierhttp://arxiv.org/abs/math/0601293
dc.identifierDiscrete Mathematics & Theoretical Computer Science 10(1):27-34, 2008
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/168647
dc.subjectCombinatorics
dc.subject05C62
dc.titleBounded-Degree Graphs have Arbitrarily Large Queue-Number
dc.typetext

Files

Collections

arXiv