Large induced forests in planar graphs with girth 4

被引：5

作者：

Dross, Francois ^{[1
]}

Montassier, Mickael ^{[1
]}

Pinlou, Alexandre ^{[1
]}

机构：

[1] Univ Montpellier, LIRMM, 161 Rue Ada, F-34095 Montpellier 5, France

来源：

DISCRETE APPLIED MATHEMATICS | 2019年 / 254卷

关键词：

Planar graphs; Triangle-free planar graphs; Induced forests; Feedback vertex sets; Albertson-Berman conjecture;

D O I：

10.1016/j.dam.2018.06.029

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

We give a new lower bound on the order of a largest induced forest in planar graphs with girth 4. We prove that a triangle-free planar graph of order n admits an induced forest of order at least 6n+7/11 , improving the lower bound of Salavatipour (2006). (C) 2018 Elsevier B.V. All rights reserved.

引用

页码：96 / 106

页数：11

共 14 条

[1] MAXIMUM INDUCED FORESTS OF PLANAR GRAPHS [J].

AKIYAMA, J ;

WATANABE, M .

GRAPHS AND COMBINATORICS, 1987, 3 (02) :201-202

[2]

Albertson M.O., 1979, GRAPH THEORY RELATED

[3]

Albertson M.O., 1998, PROBLEM RAISED DIMAC

[4] Large induced forests in sparse graphs [J].

Alon, N ;

Mubayi, D ;

Thomas, R .

JOURNAL OF GRAPH THEORY, 2001, 38 (03) :113-123

[5]

Alon N., 2003, DISCRETE MATH

[6]

[Anonymous], 1972, P COMPLEXITY COMPUTE

[7]

BORODIN OV, 1976, DOKL AKAD NAUK SSSR+, V231, P18

[8] Short Proofs of Some Extremal Results [J].

Conlon, David ;

Fox, Jacob ;

Sudakov, Benny .

COMBINATORICS PROBABILITY & COMPUTING, 2014, 23 (01) :8-28

[9] Minimum feedback vertex set and acyclic coloring [J].

Fertin, G ;

Godard, E ;

Raspaud, A .

INFORMATION PROCESSING LETTERS, 2002, 84 (03) :131-139

[10]

Hosono K., 1990, Proc. Fac. Sci. Tokai Univ., V25, P27

← 1 2 →