I am trying some methods to solve the graph coloring problem with large data sets. I decided to start off with the total space search but to eliminate certain combinations that are same due to symmetry. So for instance, if we code the color by a natural number, graph coloring 1-2-1-1 is the same as the coloring 2-1-2-2.
I figured that all the colorings from the same symmetry group can be represented by their member which has all the colors first time appearing in the correct order. For instance in the graph 1-2-1-2-4-3 the appearances of colors is 1, 2, 4, 3 which is not in order. So the colorings 1-2-1-1, 2-1-2-2, 3-1-3-3 are all the same as 1-2-1-1 and I do not even allow the others in the search.
In the implementation I go node by node and if at some node in the search $\gamma$ colors appeared so far, I try out only colors $[1, \gamma + 1]$. I testes for some small cases but for larger cases since I am using some data set with best found solutions noted, it seems that better results are possible though I think I am doing the full space search with symmetry applied. My question is why is this happening and where does my solution method skip the combinations. I really tried hard and could not figure it out. It seems to me idea is fine.
Here is the pseudocode of my algorithm. A bit of clarification. Since I am using depth first I edit the original globally defined graph as a solution for each level.
Graph G best_coloring find_solution(curr_node = 0, gamma = 1): if curr_node == G.node_count: # base case if colors_used < colors_used(best_coloring): best_coloring = G else: for color in [1, gamma]: G.nodes[curr_node].color = color if is_coloring_ok(G): if color == gamma: next_gamma = gamma + 1 else: next_gamma = gamma find_solution(curr_node + 1, next_gamma)