I am not sure if this is really a "coloring" problem as much as it is an assignment/linear-programming problem. I have zero expertise in either, so pardon any noob-ness that might follow. But I get the feeling that this problem must have almost definitely been solved/investigated before, I just couldnt find anything after looking through many of the graph algorithms on <http://en.wikipedia.org/wiki/Category:Graph_algorithms> . I was hoping to get some pointers in the right direction.

The "problem-statement" effectively boils down to :

1. There are two types of vertices in the graph : routers and cores.
2. Cores are connected to routers ONLY. Each core is connected only to a SINGLE router. And each has a user-inputed/defined "color". (In my specific problem the color is limited to one of say 4/5 possible colors). Their color cannot be changed, it is an input parameter. (Cores are the squares in the image below)
3. Routers are connected to cores as well as other routers. They do not have a "color" assigned to them. Assigning a color is part of the objective of the program/algorithm. (Routers are the circular vertices in the image below.)
4. The objective of the program is to assign colors to each router in the graph such that the number of "crossings"/edges between vertices of a different colors are minimized.

(An alternative view : In essence you are given a graph where some vertices are colored, others are not. The objective is to color the ones that are not such that the number of edges between vertices of different color is minimized.)

I was able to formulate this (quite poorly I am sure) as an Integer-Linear-Program and have setup a solution/approach using LP-Solve. I also have a heuristic of my own. I would love to know the "proper"/known/other approaches towards solving this?!

Many Thanks!

![Trivial example for demonstration.](https://i.stack.imgur.com/acYPy.png)