- Series
- Graph Theory Seminar
- Time
- Tuesday, September 24, 2013 - 12:05pm for 1 hour (actually 50 minutes)
- Location
- Skiles 005
- Speaker
- Zdenek Dvorak – Charles University
- Organizer
- Robin Thomas

By the 4-color theorem, every planar graph on n vertices has
an independent set of size at least n/4. Finding a simple
proof of this fact is a long-standing open problem.
Furthermore, no polynomial-time algorithm to decide whether
a planar graph has an independent set of size at least (n+1)/4
is known.
We study the analogous problem for triangle-free planar graphs.
By Grotzsch' theorem, each such graph on n vertices has an
independent set of size at least n/3, and this can be easily
improved to a tight bound of (n+1)/3. We show that for every k,
a triangle-free planar graph of sufficiently large tree-width has
an independent set of size at least (n+k)/3, thus giving a polynomial-time
algorithm to decide the existence of such a set. Furthermore,
we show that there exists a constant c < 3 such that every planar graph
of girth at least five has an independent set of size at least n/c.Joint work with Matthias Mnich.