Friday, December 11th, 2015 4pm-5pm McConnell 103
Charles University
Independent sets in triangle-free planar graphs

Let G be an n-vertex planar triangle-free graph. Since G is 3-colorable, it has an independent set of size at least n/3. This lower bound can be improved to (n+1)/3. We describe all graphs matching the improved bound and discuss other related questions.

Fall 2015 Schedule