Premium
Large Induced Forests in Graphs
Author(s) -
Shi Lingsheng,
Xu Hongyu
Publication year - 2017
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22104
Subject(s) - combinatorics , mathematics , planar graph , tree depth , trémaux tree , discrete mathematics , graph , vertex (graph theory) , line graph , 1 planar graph , pathwidth
In this article, we prove three theorems. The first is that every connected graph of order n and size m has an induced forest of order at least ( 8 n − 2 m − 2 ) / 9 with equality if and only if such a graph is obtained from a tree by expanding every vertex to a clique of order either 4 or 5. This improves the previous lower bound2 n 22 m + nof Alon–Kahn–Seymour for m ≤ 5 n / 2 , and implies that such a graph has an induced forest of order at least n / 2 for m < ⌊ 7 n / 4 ⌋ . This latter result relates to the conjecture of Albertson and Berman that every planar graph of order n has an induced forest of order at least n / 2 . The second is that every connected triangle‐free graph of order n and size m has an induced forest of order at least ( 20 n − 5 m − 5 ) / 19 . This bound is sharp by the cube and the Wagner graph. It also improves the previous lower bound n − m / 4 of Alon–Mubayi–Thomas for m ≤ 4 n − 20 , and implies that such a graph has an induced forest of order at least 5 n / 8 for m < ⌊ 13 n / 8 ⌋ . This latter result relates to the conjecture of Akiyama and Watanabe that every bipartite planar graph of order n has an induced forest of order at least 5 n / 8 . The third is that every connected planar graph of order n and size m with girth at least 5 has an induced forest of order at least ( 8 n − 2 m − 2 ) / 7 with equality if and only if such a graph is obtained from a tree by expanding every vertex to one of five specific graphs. This implies that such a graph has an induced forest of order at least 2 ( n + 1 ) / 3 , where 7 n / 10 was conjectured to be the best lower bound by Kowalik, Lužar, and Škrekovski.