1. Triangle-free planar graphs with the smallest independence number
- Author
-
Zdeněk Dvořák, Ondřej Pangrác, Jan Musílek, and Tomáš Masařík
- Subjects
Class (set theory) ,010102 general mathematics ,0102 computer and information sciences ,Computer Science::Computational Geometry ,01 natural sciences ,Graph ,Planar graph ,Combinatorics ,symbols.namesake ,Planar ,010201 computation theory & mathematics ,Independent set ,symbols ,Discrete Mathematics and Combinatorics ,Geometry and Topology ,0101 mathematics ,Independence number ,Mathematics - 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.
- Published
- 2018
- Full Text
- View/download PDF