Skip to Main content Skip to Navigation
Journal articles

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.
Document type :
Journal articles
Complete list of metadata

Cited literature [10 references]  Display  Hide  Download

https://hal.inria.fr/hal-00990440
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Submitted on : Thursday, June 12, 2014 - 10:48:43 AM
Last modification on : Monday, June 8, 2020 - 12:08:06 PM
Long-term archiving on: : Friday, September 12, 2014 - 10:37:52 AM

File

1323-4944-2-PB.pdf
Explicit agreement for this submission

Identifiers

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

Share

Metrics

Record views

206

Files downloads

1251