If you see the above graph, no nodes next to each other has the same color. I created a grid graph with diagonal edges across nodes using networkx python and applied greedy color to it.

greed = nx.coloring.greedy_color(G)
print(greed)

which gives the output

{(1, 1): 0, (1, 2): 1, (1, 3): 0, (1, 4): 1, (1, 5): 0, (1, 6): 1, (1, 7): 0, (1, 8): 1, (2, 1): 2, (2, 2): 3, (2, 3): 2, (2, 4): 3, (2, 5): 2, (2, 6): 3, (2, 7): 2, (2, 8): 3, (3, 1): 0, (3, 2): 1, (3, 3): 0, (3, 4): 1, (3, 5): 0, (3, 6): 1, (3, 7): 0, (3, 8): 1, (4, 1): 2, (4, 2): 3, (4, 3): 2, (4, 4): 3, (4, 5): 2, (4, 6): 3, (4, 7): 2, (4, 8): 3, (5, 1): 0, (5, 2): 1, (5, 3): 0, (5, 4): 1, (5, 5): 0, (5, 6): 1, (5, 7): 0, (5, 8): 1, (6, 1): 2, (6, 2): 3, (6, 3): 2, (6, 4): 3, (6, 5): 2, (6, 6): 3, (6, 7): 2, (6, 8): 3, (7, 1): 0, (7, 2): 1, (7, 3): 0, (7, 4): 1, (7, 5): 0, (7, 6): 1, (7, 7): 0, (7, 8): 1, (8, 1): 2, (8, 2): 3, (8, 3): 2, (8, 4): 3, (8, 5): 2, (8, 6): 3, (8, 7): 2, (8, 8): 3, (0, 1): 2, (0, 2): 3, (0, 3): 2, (0, 4): 3, (0, 5): 2, (0, 6): 3, (0, 7): 2, (0, 8): 3, (1, 0): 1, (1, 9): 0, (2, 0): 3, (2, 9): 2, (3, 0): 1, (3, 9): 0, (4, 0): 3, (4, 9): 2, (5, 0): 1, (5, 9): 0, (6, 0): 3, (6, 9): 2, (7, 0): 1, (7, 9): 0, (8, 0): 3, (8, 9): 2, (9, 1): 0, (9, 2): 1, (9, 3): 0, (9, 4): 1, (9, 5): 0, (9, 6): 1, (9, 7): 0, (9, 8): 1, (0, 0): 3, (0, 9): 2, (9, 0): 1, (9, 9): 0}

after sorting

{(0, 0): 3, (0, 1): 2, (0, 2): 3, (0, 3): 2, (0, 4): 3, (0, 5): 2, (0, 6): 3, (0, 7): 2, (0, 8): 3, (0, 9): 2, (1, 0): 1, (1, 1): 0, (1, 2): 1, (1, 3): 0, (1, 4): 1, (1, 5): 0, (1, 6): 1, (1, 7): 0, (1, 8): 1, (1, 9): 0, (2, 0): 3, (2, 1): 2, (2, 2): 3, (2, 3): 2, (2, 4): 3, (2, 5): 2, (2, 6): 3, (2, 7): 2, (2, 8): 3, (2, 9): 2, (3, 0): 1, (3, 1): 0, (3, 2): 1, (3, 3): 0, (3, 4): 1, (3, 5): 0, (3, 6): 1, (3, 7): 0, (3, 8): 1, (3, 9): 0, (4, 0): 3, (4, 1): 2, (4, 2): 3, (4, 3): 2, (4, 4): 3, (4, 5): 2, (4, 6): 3, (4, 7): 2, (4, 8): 3, (4, 9): 2, (5, 0): 1, (5, 1): 0, (5, 2): 1, (5, 3): 0, (5, 4): 1, (5, 5): 0, (5, 6): 1, (5, 7): 0, (5, 8): 1, (5, 9): 0, (6, 0): 3, (6, 1): 2, (6, 2): 3, (6, 3): 2, (6, 4): 3, (6, 5): 2, (6, 6): 3, (6, 7): 2, (6, 8): 3, (6, 9): 2, (7, 0): 1, (7, 1): 0, (7, 2): 1, (7, 3): 0, (7, 4): 1, (7, 5): 0, (7, 6): 1, (7, 7): 0, (7, 8): 1, (7, 9): 0, (8, 0): 3, (8, 1): 2, (8, 2): 3, (8, 3): 2, (8, 4): 3, (8, 5): 2, (8, 6): 3, (8, 7): 2, (8, 8): 3, (8, 9): 2, (9, 0): 1, (9, 1): 0, (9, 2): 1, (9, 3): 0, (9, 4): 1, (9, 5): 0, (9, 6): 1, (9, 7): 0, (9, 8): 1, (9, 9): 0}

But I want it to be in such a way that no two adjacent/neighbor nodes to a node should have the same color

In the above figure, (1,4) [green] has its neighbors (1,3) [red] and (1,5) [red]. In this case both nodes next to node (1,4) are red. But I want (1,3) and (1,5) in different colors. Can anyone tell me how to solve this problem?

I tried greedy color method from networkx to color in such a way that no two nodes adjacent to each other have the same color.

CodePudding user response：

Have you tried the Graph Coloring algorithm?

Step 1 − Arrange the vertices of the graph in some order.

Step 2 − Choose the first vertex and color it with the first color.

Step 3 − Choose the next vertex and color it with the lowest numbered color that has not been colored on any vertices adjacent to it. If all the adjacent vertices are colored with this color, assign a new color to it. Repeat this step until all the vertices are colored.

credits : https://www.tutorialspoint.com/the-graph-coloring

CodePudding user response：

The problem is that you have an additional constraint that the coloring algorithm does not respect. You have two choice : change the algorithm to respect the constraint (hard), change the data (the graph) so that the constraints are integrated in it.

The second option is really easy to do here. All we have to do is add edges between nodes that should not be the same color (that is, nodes that share a common neighbor), color the graph.

1. Create a deep copy G2 of the graph G. As we will modify the graph to match the new constraints, we have to keep the original intact.
2. For every pair of nodes n_1, n_2 in G :
   1. If they are adjacent, nothing to do.
   2. If they share a common neighbor in G, add an edge (n_1, n_2) in G2
3. Color G2
4. For every node in G, set it's color to the color of the corresponding node in G2