Georgia Institute of Technology College of Sciences

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.