Color a graph using k colors, k>4, with the most equal distribution of colors Given a planar graph G with $N$ nodes, 4 colors are enough to color each node, so that adjacent nodes have different colors.

Let $k &gt; 4$. Is there an algorithm to color the nodes with $k$ colors, so that the colors are distributed the most equally possible?

In other words:

Let's call $c_1, ..., c_k$ the colors. We define
$\forall c_k\in[1,k], f(c_k)=\textrm{number of nodes of color}c_k$. Obviously, $\sum f(c_k) = N$. Find an algorithm to color the $N$ node with the $k$ colors to maximize the value $\min f$, with 2 adjacent nodes having different colors.
You are perhaps looking for an equitable coloring, which is a proper coloring where the size of any two color classes differ by at most one. Finding an equitable 3-coloring is NP-complete for planar graphs.