An improved bound on the largest induced forests for triangle-free planar graphs

Abstract : We proved that every planar triangle-free graph of order n has a subset of vertices that induces a forest of size at least (71n + 72)/128. This improves the earlier work of Salavatipour (2006). We also pose some questions regarding planar graphs of higher girth.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2010, 12 (1), pp.87-100
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00990440
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : jeudi 12 juin 2014 - 10:48:43
Dernière modification le : mercredi 29 novembre 2017 - 10:26:22
Document(s) archivé(s) le : vendredi 12 septembre 2014 - 10:37:52

Fichier

1323-4944-2-PB.pdf
Accord explicite pour ce dépôt

Identifiants

  • HAL Id : hal-00990440, version 1

Collections

Citation

Lukasz Kowalik, Borut Luzar, Riste Skrekovski. An improved bound on the largest induced forests for triangle-free planar graphs. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2010, 12 (1), pp.87-100. 〈hal-00990440〉

Partager

Métriques

Consultations de la notice

147

Téléchargements de fichiers

314