6
$\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$
4
  • $\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$ Mar 24, 2014 at 20:44
  • 2
    $\begingroup$ IMHO it gets nontrivial if you request the graph to be 3-connected, as well. $\endgroup$ Mar 24, 2014 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$ Mar 25, 2014 at 6:52
  • $\begingroup$ OK, I was thinking about the maximum ratio, sorry. $\endgroup$ Mar 25, 2014 at 8:44

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.