The independence ratio is defined as the size of the maximum independent set divided by $n$. By the 4-color theorem, every planar graph with $n$ vertices has independence ratio at least $1/4$. Clearly, this bound is tight, since the $K_4$ is planar and admits no independent set with more than $n/4=1$ vertex. Arbitrarily large planar graphs with independence ratio $1/4$ can be constructed by connecting many copies of the $K_4$.

My main question is: *What is the minimum independence ratio of planar graphs that do not contain the $K_4$ as a subgraph? Are there interesting lower bounds and upper bounds?*

I would also be interested in the more restricted class of *matchstick graphs*, which are planar graphs that can be drawn with non-crossing unit-length straight edges. These are K4-free and planar, but not all K4-free planar graphs are matchstick graphs.

minimumindependence ratio inside a graph class. The 3-connected question is probably non-trivial, but not exactly what I'm interested at. $\endgroup$ – Guilherme D. da Fonseca Mar 25 '14 at 6:52