# 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 > 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.

• Sure there is an algorithm: try all possible $k$-colorings and pick the best one (if any). – Juho Dec 1 '18 at 23:00