Triangle-free planar graphs with the smallest independence number

Abstract

Steinberg and Tovey proved that every n-vertex planar triangle-free graph has an independent set of size at least (n + 1)/3, and described an infinite class of tight examples. We show that all n-vertex planar triangle-free graphs except for this one infinite class have independent sets of size at least (n + 2)/3.

Keywords

• independent set
• planar graph
• triangle-free