Finding k-coloring (with k = 2/3) graph in linear time

Question

Question:

Given a graph G = (V,E) a k-coloring of G is a labeling of the vertices with the colors c_1, c_2, ..., c_k such that for every edge (u,v) the color of 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 two colors so that you have the maximum number of nodes colored c_1. Prove that your algorithm from part (a), with a minor modification probably, can be used to solve this problem. Be precise.

C. Show an example of a tree, T, that can have at most j nodes colored c_1 in a 2-coloring but T can have j' > j nodes colored c_1 in a 3-coloring. Try to find the smallest example of such a tree T.

D. Give a linear time dynamic programming algorithm that creates a 3-coloring for a tree such that the maximum number of nodes are colored c_1. Justify your answer.

What I have:

Parts A and B seem rather simple, but I am struggling on C and D

A. This seems simple, run DFS, but modify it so if it

1. encounters an uncolored node color it c1 and its children c2,

2. encounters a colored node color its children the opposite color

3. if it ever tries to "flip" the color of a child, then return that it is impossible to have k-coloring

This is just DFS, so will run at O(V+E)

Edit: Since this a tree you can call BFS on a random node, alternating colors in the BFS

B. Since this is a binary first choice (ie c1 or c2) and all choices follow from the first choice, we can simply calculate which is superior coloring the first node c1 or c2. We can do this by adding a counter to the above algorithm calculating the number of c1 nodes. Run the algorithm twice once starting with c1, then with c2, compare the number of c1 nodes between the two, and then pick the graph with more c1 nodes

C. Been fiddling with this for a while and can't find a single one, much less the smallest one possible

Edit: 1-3, 2-3, 3-4, 4-5, 4-6 described by Bing Wang works here

D. No idea. I assume you are going to have to be using a modified DFS to have it run at linear, but am extremely unsure beyond that. I can come up with ways to brute force it, but nothing that runs at linear.

Edit: Still confused about this

Answer 1

c: 1-3, 2-3, 3-4, 4-5,4-6. This tree can have 3 nodes in each color in bi-color. But can have 4 nodes in the same color if you color node #3/#4 to two other colors - in a tri-color. You should be easily prove no smaller answer by going over all possibilities.

D: Just traverse the tree, e.g. DFS. Each node needs to keep c_1 count of all 3 colorings. WHen you deal with 1st node, that would be (1,0,0) - fairly easy count. Once you add the nodes into the visited, try all 3 colors, each color would be compatible with 2 colors of the connecting node, from which you pick the bigger one, etc, to construct the 3 values of current node.

E=[(1,3),(2,3),(3,4),(4,5),(4,6)]
V={v:set() for e in E for v in e}
[None if V[e[0]].add(e[1]) else V[e[1]].add(e[0]) for e in E]
serialized={}
def traverse(c):
    serialized[c]=V[c]
    [traverse(n) for n in V[c] if n not in serialized]
    
traverse(E[0][0])
visited=set()
for k,v in reversed(serialized.items()):
    filtered=v.intersection(visited)
    visited.add(k)
    m=[1+sum(max([V[child][1],V[child][2]]) for child in filtered)
        ,sum(max([V[child][0],V[child][2]]) for child in filtered)
        ,sum(max([V[child][0],V[child][1]]) for child in filtered)]
    V[k]=m
print(max(V[k]))