Maximal planar graphs with minimum independent sets

18 Views Asked by At

The lower bound is known to follow immediately from the Four Color Theorem.

Theorem 1. If $G$ is a planar graph with order $n$, then $\alpha(G) \geq \frac{n}{4}$.

The lower bound in Theorem 1 is sharp. We can choose $\frac{n}{4}$ number of disjoint copies of $K_4$ as an extremal graph, and so is any graph formed by adding edges while preserving planarity. But how about maximal planar graphs, can we construct an $n$-vertex maximal planar graph where $n$ can be arbitrarily large?

Furthermore, is the characterization done by such extremal (maximal) planar graphs?

Is there a review article on independent sets? Independent sets seem to have a long history, but there appears to be relatively limited theoretical research and tools compared to matching problems, making them less mature.