4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Do you want to restrict to connected graphs? Otherwise, a bunch of non-connected vertices is as best as you can hope for. $\endgroup$ – Dima Pasechnik Mar 24 '14 at 20:44
  • 2
    $\begingroup$ IMHO it gets nontrivial if you request the graph to be 3-connected, as well. $\endgroup$ – Dima Pasechnik Mar 24 '14 at 20:46
  • $\begingroup$ 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. $\endgroup$ – Guilherme D. da Fonseca Mar 25 '14 at 6:52
  • $\begingroup$ OK, I was thinking about the maximum ratio, sorry. $\endgroup$ – Dima Pasechnik Mar 25 '14 at 8:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.