Given a graph G with V nodes and V different colors, I would like to assign colors to these nodes such that the color assigned to a node is as visually distinct as it can get from all of its neighbors. All V colors must be assigned to the V nodes.
I have tried using a greedy approach in the CIELAB color space to calculate distances between the colors as follows:
Traverse the graph in a breadth first manner
Process a node. While processing a node, check which neighbors have been assigned a color. The first node gets assigned a random color.
Find a color from the existing V colors that is maximally distinct from the neighboring colors.
Assign that color to the current node.
Iterate through steps 2-4
This algorithm does not yield good results. What I wish to have is all colors being used in the graph such that every node is distinct from its neighbors. Maybe this can be thought of as an optimization problem where we are trying to maximize the difference between two nodes along an edge. Any guidance on this will be appreciated! Thanks!