Large Induced Forests in Graphs |
| |
Authors: | Lingsheng Shi Hongyu Xu |
| |
Institution: | 1. DEPARTMENT OF MATHEMATICAL SCIENCES, TSINGHUA UNIVERSITY, BEIJING, CHINAContract grant sponsor: National Natural Science Foundation of China;2. Contract grant number: 91338102;3. DEPARTMENT OF MATHEMATICAL SCIENCES, TSINGHUA UNIVERSITY, BEIJING, CHINA |
| |
Abstract: | 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 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 bound of Alon–Kahn–Seymour for , and implies that such a graph has an induced forest of order at least for . 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 . The second is that every connected triangle‐free graph of order n and size m has an induced forest of order at least . This bound is sharp by the cube and the Wagner graph. It also improves the previous lower bound of Alon–Mubayi–Thomas for , and implies that such a graph has an induced forest of order at least for . 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 . 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 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 , where was conjectured to be the best lower bound by Kowalik, Lu?ar, and ?krekovski. |
| |
Keywords: | acyclic set girth induced forest planar graph triangle‐free |
|
|