Here is an algorithm that could work and run reasonably quickly, although it might not be optimal:
1. Find all vertices with degree N > 40 (eg: find all points in the graph with more than 40 outgoing edges).
2. For each pair (a, b) of these degree N > 40 vertices, find the set of common points (c) connected to both a and b by edges, eg: there exists 2 edges (a - c) and (b - c). In essence, you're forming V shapes (a - c - b) where the two tips (a, b) of the V have at least N > 40 outgoing edges.
3. Identify the pairs of vertices (a, b) that are connected by 40 or more Vs (eg: there are at least 40 pairs of (a - c) and (b - c) edges).
4. Remove the (a - c) or (b - c) edge with the highest weight. If (a - c) and (b - c) have equal weight, remove the edge which is connected to the node a or b with more outgoing edges.
5. Repeat steps 3 and 4 until each (a, b) pair has at most 39 Vs connecting them together.
At this point, I think you can color the graph with N=40 colors (one color for a and b, then different colors for each in-between point of the 39 Vs between them).
There might be a way to improve the criteria for which edge to remove in step 4 (maybe using the backtracking approach mentioned by other commenters), but this should be a decent starting point.
1. Find all vertices with degree N > 40 (eg: find all points in the graph with more than 40 outgoing edges).
2. For each pair (a, b) of these degree N > 40 vertices, find the set of common points (c) connected to both a and b by edges, eg: there exists 2 edges (a - c) and (b - c). In essence, you're forming V shapes (a - c - b) where the two tips (a, b) of the V have at least N > 40 outgoing edges.
3. Identify the pairs of vertices (a, b) that are connected by 40 or more Vs (eg: there are at least 40 pairs of (a - c) and (b - c) edges).
4. Remove the (a - c) or (b - c) edge with the highest weight. If (a - c) and (b - c) have equal weight, remove the edge which is connected to the node a or b with more outgoing edges.
5. Repeat steps 3 and 4 until each (a, b) pair has at most 39 Vs connecting them together.
At this point, I think you can color the graph with N=40 colors (one color for a and b, then different colors for each in-between point of the 39 Vs between them).
There might be a way to improve the criteria for which edge to remove in step 4 (maybe using the backtracking approach mentioned by other commenters), but this should be a decent starting point.