Independent sets in triangle-free cubic planar graphs

We prove that every triangle-free planar graph on n vertices with maximum degree three has an independent set with size at least 3 8 n . This was suggested and later conjectured by Albertson, Bollobás, and Tucker.

Saved in:
Bibliographic Details
Published in:Journal of combinatorial theory. Series B 2006-03, Vol.96 (2), p.253-275
Main Authors: Heckman, Christopher Carl, Thomas, Robin
Format: Article
Language:English
Subjects:
Graph
Independent set
Maximum degree three
Planar graph
Stable set
Triangle-free
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We prove that every triangle-free planar graph on n vertices with maximum degree three has an independent set with size at least 3 8 n . This was suggested and later conjectured by Albertson, Bollobás, and Tucker.
ISSN:0095-8956
1096-0902
DOI:10.1016/j.jctb.2005.07.009