What are some theorems giving lower bounds on the size of a maximum indepedent set of verticies of a planar graph?

118 Views Asked by At

Suppose that $G$ is a planar graph. What is an example of a theorem that will give us a lower bound on the size of a maximum independent set of vertices in $G$?

The following may or may not be true, but as an example, we want something like,

If $G$ has $n$ vertices, there there exists an independent set in G containing at least $n/4$ vertices.

1

There are 1 best solutions below

1
On

For any graph $G$, let $\alpha(G)$ denote maximum number of vertices in an independent set in $G$.

Sometime between 1974 & 1976 Michael O'Albertson proved:

If G is a planar graph then $\alpha(G)/N \geq 2/9$.

However, that very slightly pre-dated the proof of the 4-color theorem, in 1976, by Kenneth Appel and Wolfgang Haken.

A corollary of 4-color theorem is that:

If G is a planar graph then $\alpha(G)/N \geq 1/4$.

$1/4 > 2/9$