# A graph coloring problem concerning 3-colorablility

If I take a triangle-free graph, By Grötzsch's theorem, it should be 3-colorable, and I have already had a coloring. If I change the color of one vertex, and I want to check how many vertices (at least) do I need to change, and I cannot find an idea on writing an algorithm to find out. I know that by symmetry, I can exchange two colors, I will get a new coloring method, it gives an upper bound. But it cannot give me any idea about the algorithm.

Is there any hint or literature to help me? Thanks for your attention!

-
Grötzsch's theorem only applies to planar graphs. –  Chris Godsil Jan 3 '13 at 16:18
@ChrisGodsil I see,but what I need is the algorithm to find the number of nodes which I need to change color.. –  Golbez Jan 4 '13 at 2:44
@Golbez As Chris said Grotzsch's theorem doesn't guarantee the graph is $3$-colorable unless it's planar, so are you assuming that the graph is planar now? Or are you just assuming it's $3$-colorable? –  Alexander Gruber Jan 5 '13 at 23:45
And what exactly do you mean by "how many nodes do I need to change"? –  Alexander Gruber Jan 5 '13 at 23:46

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|\}$:
1. 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.
2. Iterate through all $2^{|S_k|}$ possible assignments of new colours to the vertices in $S_k$.
3. 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.
4. 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.

-