Independence number n/4 in planar graphs
Open Problem (independence number of planar graphs) · arXiv:1702.02888
Status open high confidence
The open problem asks for a structural characterisation of planar graphs on $n$ vertices whose independence number is exactly $n/4$, and whether there is a polynomial-time algorithm to decide if an $n$-vertex planar graph has an independent set larger than $n/4$. No follow-up paper resolving either question was found in a targeted web search across arXiv and related databases. The maximum independent set problem is NP-hard on planar graphs in general, but the specific decision problem at the n/4 threshold—which is the Four Colour Theorem's trivial lower bound—remains open, and its complexity (polynomial vs. NP-hard) appears unresolved.
Reviewer notes. No follow-up paper resolving either part of the open problem was found after 5 web calls (3 WebSearch + 2 WebFetch attempts including Semantic Scholar). The conjecture is recent (2017) and concerns a subtle threshold question distinct from the known NP-hardness of maximum independent set on planar graphs. Status open with high confidence.
Context
By the Four Colour Theorem every planar graph is 4-colourable, giving an independent set of size at least $n/4$, and there are infinitely many planar graphs for which this bound is tight. The paper studies the easier related problem for triangle-free planar graphs (where Grötzsch's theorem raises the bound to $n/3$) as a tractable surrogate for this harder general question.
Notes. Stated in prose in the introduction without a labelled environment and without attribution to specific prior authors; the full paper text is truncated after Corollary 17's proof, so further conjectures or problems in Sections 2–4 may be missing.
Source paper
Triangle-free planar graphs with small independence number
Zdeněk Dvořák, Jordan Venters · 2017-02-09
https://arxiv.org/abs/1702.02888
PDF source