Discrete Mathematics & Theoretical Computer Science, Vol 10, No 1 (2008)

Font Size:  Small  Medium  Large

Bounded-Degree Graphs have Arbitrarily Large Queue-Number

David R. Wood


It is proved that there exist graphs of bounded degree with arbitrarily large queue-number. In particular, for all Δ ≥ 3 and for all sufficiently large n, there is a simple Δ-regular n-vertex graph with queue-number at least c √Δ n1/2-1/Δ for some absolute constant c.

Full Text: PDF PostScript