Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. An improved bound on ...
Article

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

Lukasz Kowalik (1), Borut Luzar (2), Riste Skrekovski (2)
(1) Institute of Informatics [Warsaw]
(2) Faculty of Mathematics and Physics [Ljubljana]
Download article
Open on HAL
Imported on
March 26, 2015
Published on
January 1, 2010
Last modified on
March 31, 2025
Volume 12
vol. 12:1
DOI
10.46298/dmtcs.487
License
https://about.hal.science/hal-authorisation-v1
Indicators
1151
Views
2109
Downloads

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

Lukasz Kowalik (1), Borut Luzar (2), Riste Skrekovski (2)
(1) Institute of Informatics [Warsaw]
(2) Faculty of Mathematics and Physics [Ljubljana]
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.
Keywords
  • [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
  • Induced forest
  • Forest number
  • Decycling number
Cited by

Source: OpenCitations

  • Minimum size of feedback vertex sets of planar graphs of girth at least five

    European Journal of Combinatorics

    Authors : Tom Kelly ORCID, Chun-Hung Liu ORCID

    Journal reference : Volume 61, 2016, pp. 138-150

    DOI : 10.1016/j.ejc.2016.10.009

  • Short Proofs of Some Extremal Results

    DSpace@MIT (Massachusetts Institute of Technology)

    Authors : DAVID CONLON ORCID, JACOB FOX ORCID, BENNY SUDAKOV ORCID

    Journal reference : Volume 23, 2013, pp. 8-28

    DOI : 10.1017/s0963548313000448

  • Size of the largest induced forest in subcubic graphs of girth at least four and five

    Journal of Graph Theory

    Authors : Tom Kelly ORCID, Chun‐Hung Liu ORCID

    Journal reference : Volume 89, 2018, pp. 457-478

    DOI : 10.1002/jgt.22361

  • A lower bound on the order of the largest induced forest in planar graphs with high girth

    Discrete Applied Mathematics

    Authors : François Dross ORCID, Mickael Montassier, Alexandre Pinlou ORCID

    Journal reference : Volume 214, 2016, pp. 99-107

    DOI : 10.1016/j.dam.2016.06.011
Preview
Loading PDF preview...