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

被引：1

作者：

Kowalik, Lukasz ^{[1
]}

Luzar, Borut ^{[2
]}

Skrekovski, Riste ^{[2
]}

机构：

[1] Warsaw Univ, Inst Informat, PL-02097 Warsaw, Poland

[2] Inst Math Phys & Mech, Ljubljana 1111, Slovenia

来源：

DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE | 2010年 / 12卷 / 01期

关键词：

Induced forest; Forest number; Decycling number; INDUCED TREES;

D O I：

暂无

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

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.

引用

页码：29 / 42

页数：14

共 10 条

[1] MAXIMUM INDUCED FORESTS OF PLANAR GRAPHS
AKIYAMA, J
WATANABE, M
[J]. GRAPHS AND COMBINATORICS, 1987, 3 (02) : 201 - 202
[2] Albertson M. O., 1979, GRAPH THEORY REL TOP, P357
[3] Problems and results in extremal combinatorics - I
Alon, N
[J]. DISCRETE MATHEMATICS, 2003, 273 (1-3) : 31 - 53
[4] Large induced forests in sparse graphs
Alon, N
Mubayi, D
Thomas, R
[J]. JOURNAL OF GRAPH THEORY, 2001, 38 (03) : 113 - 123
[5] MAXIMUM INDUCED TREES IN GRAPHS
ERDOS, P
SAKS, M
SOS, VT
[J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 1986, 41 (01) : 61 - 79
[6] Large induced trees in Kr-free graphs
Fox, Jacob
Loh, Po-Shen
Sudakov, Benny
[J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 2009, 99 (02) : 494 - 501
[7] Karp R.M., 1972, PLENUM PRESS SURV ST, P85, DOI 10.1007/978-1-4684-2001-2_9
[8] Matousek J, 2008, ELECTRON J COMB, V15
[9] Punnim N, 2006, THAI J MATH, V4, P145
[10] Large induced forests in triangle-free planar graphs
Salavatipour, MR
[J]. GRAPHS AND COMBINATORICS, 2006, 22 (01) : 113 - 126

← 1 →