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!

  • 2
    $\begingroup$ Grötzsch's theorem only applies to planar graphs. $\endgroup$ Jan 3, 2013 at 16:18
  • $\begingroup$ @ChrisGodsil I see,but what I need is the algorithm to find the number of nodes which I need to change color.. $\endgroup$
    – Golbez
    Jan 4, 2013 at 2:44
  • $\begingroup$ @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? $\endgroup$
    – Alexander Gruber
    Jan 5, 2013 at 23:45
  • $\begingroup$ And what exactly do you mean by "how many nodes do I need to change"? $\endgroup$
    – Alexander Gruber
    Jan 5, 2013 at 23:46

1 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.