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.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2008, 10 (1), pp.27--34
Liste complète des métadonnées

Littérature citée [29 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00972310
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : jeudi 3 avril 2014 - 16:07:50
Dernière modification le : samedi 3 mars 2018 - 01:04:58
Document(s) archivé(s) le : jeudi 3 juillet 2014 - 16:31:09

Fichier

541-2702-1-PB.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • 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〉

Partager

Métriques

Consultations de la notice

67

Téléchargements de fichiers

247