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.

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

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.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.