This could be solved using a breadth-first search approach. Basically, we look for clashes, and consider fixing them in all possible ways, then repeat until there are no clashes (without changing any earlier fixes).
At each stage, we will store a list of improper graph colourings and the set of vertices we've already attempted to fix in that colouring.
- Starting conditions:
- $\mathcal{G}_1=(G_1)$ where $G_1$ is the coloured graph with the vertex $v$ whose colour has been switched, and
- $\mathcal{V}_1=(V_1)$ where $V_1=\{v\}$.
If $G_1$ is already properly $3$-coloured, we are done, so we assume there is some improper edge.
For any vertex $u$, let $N(u)$ be the set of neighbours of $u$.
- Iteration: We define $\mathcal{G}_{i+1}$ and $\mathcal{V}_{i+1}$ from $\mathcal{G}_i$ and $\mathcal{V}_i$ as follows. For each $k \in \{1,2,\ldots,|\mathcal{G}_k|\}$:
- Let $S_k=\cup_{w \in V_k} \{u \in N(w):u \not\in V_k \text{ and } uw \text{ is an improper edge}\}$; these will be the vertices whose colours we decide during this iteration.
- Iterate through all $2^{|S_k|}$ possible assignments of new colours to the vertices in $S_k$.
- If we find a proper $3$-colouring, we store it in memory. We cannot exit just yet, since we cannot guarantee it is minimal. However, once we have found a proper colouring that changes $x$ colours, we can discard any other partial proper colourings with $\geq x$ changes.
- If there are no improper edges $uv$ with $u,v \in V_k \cup S_k$, then we have found a partial colouring that could possibly be extended to a proper $3$-colouring by modifying the colours outside of $V_k$. In this case, we include it in the next iteration; we:
- Add the modified colouring of $G_k$ to $\mathcal{G}_{i+1}$.
- Add $V_k \cup S_k$ to $\mathcal{V}_{i+1}$.
This will be an exponential time algorithm and, depending on the size of the input graph and vertex degrees, could be rather memory intensive.
