Maximal Independent Sets in Planar Triangulations

P. Francis, Abraham M. Illickan, Lijo M. Jose +1

We show that every planar triangulation on $n$ vertices has a maximal independent set of size at most $n/3$. This affirms a conjecture by Botler, Fernandes and Gutiérrez [Electron…