USA: +1 (725) 712-1730 
Sign in
Please help with the following problem. For part a, it seems like a greedy solution would work? Please give pseudocode.
Given a graph G = (V,E) a k-coloring of the graph is a labeling of the vertices with the colors c1, c2,..,ck such that for every edge (u,v) the color of the u is different from the color of v.
a. Give a linear time algorithm that finds a 2-coloring for a tree.
b. Think about coloring a tree with 2 colors so that you have the max number of nodes colored c1. Prove that the algorithm in part (a)-with a minor modification probably-can be used to solve this problem.
Expert Answer
Yes, correct. A greedy algorithm works for part (a). Here is the pseudo code:
- Let graph be G(V, E). Initialize each vertex ‘u’ of the graph with property u.VISITED = NO. This means the children of the vertex have not been completely processed yet.
- Let available colors be C1 and C2
- For every node ‘u’ in graph:
- If u.VISITED = ‘NO’:
- If u is uncolored, color it C1 and color all of its children vertices as C2
- If u is colored, then color all of its children with opposite color and put them in stack. If some child is already colored in the same color as ‘u’ then return “not possible to two-color this graph”.
- Make u.VISITED = “YES”
- Pop the stack and continue the same process.
- If u.VISITED = ‘NO’:
Explanation: A vertex is called “VISITED” (in above pseudocode) only it and its children have been colored completely. This process is similar to DFS process by using the stack. Effectively we are traversing each edge only once.
So, time complexity is linear O(|E|) where E = number of vetices in graph.
————–
(b) Notice that in every connected component of the graph, if we are starting fresh, then first vertex maybe colored in 2 ways – C1 or C2. However all the rest of the vertices have only one choice of coloring. So, there are only 2 ways of coloring a connected component of a graph using two colors.
Therefore, in order to get maximum number of vertices in color C1, we can use the following procedure:
- Using the pseudocode in part (a), color the graph.
- For each component of the graph, count the number of vertices in C1 and C2.
- If n(C2) > n(C1), then swap the colors for that component.
Time complexity: In the worst case, we may need to swap the color of every vertex. This means we have visit every vertex twice – once to count and once to recolor.
So, this is a linear step. Thus, this algorithm effectively keeps the same time complexity as part 1 which is linear.
