Linear-time balanced four-coloring conjecture for planar graphs

Let $G$ be a planar graph with $n\geq 3$ vertices. A balanced four-coloring is a proper $4$-coloring in which each color is used on fewer than $n/2$ vertices. Linear-time balanced four-coloring conjecture. One can compute a balanced four-coloring of $G$ in $O(n)$ time. The paper proves existence of such a coloring, but the conjectured linear-time algorithm remains open.