Neighborhood Structure for Graph Coloring Local Search Heuristic

Question

I am attempting to create a local search heuristic for a given greedy algorithm that attempts to 3-color a graph. This greedy algorithm can get stuck (ie, can color no more vertices), at which point my heuristic is used to slightly modify the current graph coloring to attempt to make more progress with the greedy algorithm. I know that I need to define a neighborhood of a given incomplete coloring, and then search through this neighborhood for better coloring candidates. My idea is to define the neighborhood as all colorings reachable by swapping two vertex colors in the graph. However, I'm a little bit confused about how to go about this. What if the coloring is such that no swaps can be made to maintain the coloring's validity? How do I select the vertices to swap?