Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.