Hi there and happy new year! :)
Colouring vertices is nothing more and nothing less than a didactic resource to explicitly distinguish among three different states:
- Nodes that have not been visited yet
- Nodes that have been visited yet not expanded
- Nodes that have been both visited and expanded
Since the state of a node does not change once a solution has been found, the notion of "de-colouring" the resulting graph is never used.
I think the above fully answers your question but let me please refer to a closely related but somehow different issue: duplicate detection. In spite of using either one strategy or another, it is usually very advantageous to avoid re-expanding nodes when it can be proven that they will not improve the cost of the incumbent solution or that they will not lead to an optimal solution. In the following, I'm covering the basics of mechanisms for duplicate detections under the strategies you mention.
When traversing a graph in Depth-First order, the only nodes in memory are those in the path from the root node to the current node. Other nodes previously expanded over which the algorithm backtracked are not in memory any more (and this is indeed the reason why this algorithm takes an amount of memory which is linear in the depth of the search tree!). Thus, the basic mechanism for avoiding duplicate detection is just to compare the child of a newly expanded node with all nodes in the current path from the root node ---just to avoid loops!
Of course, this mechanism could be enhanced by storing all nodes previously expanded but this is not trivial and doing so would lead to a much larger usage of the available memory.
In contraposition to the previous case, Breadth-First Search has a memory consumption which is exponential in the depth of the search tree. Actually, the number of nodes generated dominate the memory consumption. Hence, it is usually a good idea to use an additional data structure to avoid re-expanding nodes. In general, the preferred data structures here are sets or maps where membership operations can be performed in logarithmic time in the number of nodes previously expanded.
Hope this helps,