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 ORCID-iD

    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.


    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]

    1 Document citing this article

    Share

    Consultation statistics

    This page has been seen 239 times.
    This article's PDF has been downloaded 173 times.