MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
Do you want to restrict to connected graphs? Otherwise, a bunch of non-connected vertices is as best as you can hope for. – Dima Pasechnik Mar 24 '14 at 20:44
IMHO it gets nontrivial if you request the graph to be 3-connected, as well. – Dima Pasechnik Mar 24 '14 at 20:46
A bunch of non-connected vertices has independence ratio 1. I'm looking for the minimum independence ratio inside a graph class. The 3-connected question is probably non-trivial, but not exactly what I'm interested at. – Guilherme D. da Fonseca Mar 25 '14 at 6:52
OK, I was thinking about the maximum ratio, sorry. – Dima Pasechnik Mar 25 '14 at 8:44

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.