Lukasz Kowalik ; Borut Luzar ; Riste Skrekovski - An improved bound on the largest induced forests for triangle-free planar graphs

dmtcs:487 - Discrete Mathematics & Theoretical Computer Science, January 1, 2010, Vol. 12 no. 1 - https://doi.org/10.46298/dmtcs.487
An improved bound on the largest induced forests for triangle-free planar graphs

Authors: Lukasz Kowalik ; Borut Luzar ; Riste Skrekovski

    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.

    https://doi.org/10.46298/dmtcs.487
    Source : oai:HAL:hal-00990440v1
    Volume: Vol. 12 no. 1
    Published on: January 1, 2010
    Imported on: March 26, 2015
    Keywords: Induced forest,Forest number,Decycling number,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

    Export

    BibTeX TEI DC OpenAIRE Crossref DOAJ zbJATS JSON

    Share

    Consultation statistics

    This page has been seen 444 times.
    This article's PDF has been downloaded 343 times.