| 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.