Independent sets in triangle-free cubic planar graphs

被引：27

作者：

Heckman, CC

Thomas, R ^{[1
]}

机构：

[1] Georgia Inst Technol, Sch Math, Atlanta, GA 30332 USA

[2] Arizona State Univ, Dept Math & Stat, Tempe, AZ 85287 USA

来源：

JOURNAL OF COMBINATORIAL THEORY SERIES B | 2006年 / 96卷 / 02期

基金：

美国国家科学基金会;

关键词：

graph; planar graph; triangle-free; independent set; stable set; maximum degree three;

D O I：

10.1016/j.jctb.2005.07.009

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We prove that every triangle-free planar graph on n vertices with maximum degree three has an independent set with size at least 3/8n. This was suggested and later conjectured by Albertson, Bollobas and Tucker. (C) 2005 Elsevier Inc. All rights reserved.

引用

页码：253 / 275

页数：23

共 17 条

[1]

Albertson M., 1976, CONGRESSUS NUMERANTI, V17, P43

[2]

[Anonymous], 1979, GRADUATE TEXTS MATH

[3]

FAJTLOWICZ S., 1978, P 9 SE C COMB GRAPH, P269

[4] 11/30 (FINDING LARGE INDEPENDENT SETS IN CONNECTED TRIANGLE-FREE 3-REGULAR GRAPHS) [J].