Independent sets in graphs with an excluded clique minor

Abstract : Let G be a graph with n vertices, with independence number α, and with no Kt+1-minor for some t ≥ 5. It is proved that (2α - 1)(2t - 5) ≥ 2n - 5. This improves upon the previous best bound whenever n≥2/5t2.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2007, 9 (1), pp.171--175
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00966507
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : mercredi 26 mars 2014 - 16:59:24
Dernière modification le : samedi 3 mars 2018 - 01:04:58
Document(s) archivé(s) le : jeudi 26 juin 2014 - 11:56:11

Fichier

617-2510-1-PB.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00966507, version 1

Collections

Citation

David R. Wood. Independent sets in graphs with an excluded clique minor. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2007, 9 (1), pp.171--175. 〈hal-00966507〉

Partager

Métriques

Consultations de la notice

70

Téléchargements de fichiers

197