Discrete Mathematics & Theoretical Computer Science, Vol 12, No 1 (2010)

Font Size:  Small  Medium  Large

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

Lukasz Kowalik, Borut Lužar, Riste Škrekovski

Abstract


We proved that every planar triangle-free graph with n vertices has a subset of vertices that induces a forest of size at least (71n + 72)/128. This improves the earlier work of Salavatipour [10]. We also pose some questions regarding planar graphs of higher girth.

Full Text: PDF PostScript