[oneepic]

Similar to what another commenter said about time, have you tried a backtracking approach by: (1) coloring the whole graph (let's say you end with 42 colors) (2) start with the highest colored nodes (e.g. N=42, which exceeds your threshold of 40) and (3) greedily remove the lowest-weight edges (or maybe, edges to other high-colored nodes) until you are either all colored with 40 colors or we reach an invalid state (ie node no longer in the graph) -- with the latter you can add another edge back and try again by removing the next-lowest edge.

[graphcolorer]

That's what I'm doing now, but the results aren't great. If there's a way to estimate a lower bound on the number of edges to remove, I can figure out if the results aren't great because of the approximation, or because of the nature of the graph...