Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
2  
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

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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