Lower bounds for constant degree independent sets (Q1322210)

Suppose among the set of vertices of a graph of degree \(j\), we select the independent set of largest cardinality. Denote this cardinality by \(\alpha_ j\). Let \(\alpha^*\) be the maximum over the \(\alpha_ j\). The paper proves the following results about \(\alpha^*\), where \(v\) is the number of vertices of the graph: (1) For any tree, \(\alpha^*\geq (v+ 2)/4\). (2) \(\alpha^*\geq v/{\Delta+1\choose 2}\), where \(\Delta\) is a graph's maximum degree. (3) For a maximal planar graph, \(\alpha^*\geq (3/61)v\). (4) For any planar graph, \(\alpha^*\geq (2/65)v\).