# Tree vertex coloring algorithm to maximize the number of blue vertices

Assume that a tree $T$ is given and we want to assign a color to each vertex of it. The color should be red or blue and no adjacent vertices can have color blue. (They can both be red but not blue)

Provide a linear time algorithm to assign colors (red or blue) to the vertices of $T$ in a way that the number of blue vertices are maximized.

Any idea? I'm completely stuck... I don't know a way to start! it doesn't just want a simple coloring. It should be a coloring with maximizes the number of blue vertices. That's the entire point. How can we be sure that this condition is satisfied?

Hint: Think of the dynamic programming approach.

• Do you have any restriction on coloring? May be adjacent vertices should have different colors? – Smylic May 19 '17 at 14:48
• @Smylic Yes... i forgot to write it... i'll make an edit – Arman Malekzadeh May 19 '17 at 14:51
• @Smylic the condition is a bit different... see the question again :) – Arman Malekzadeh May 19 '17 at 15:08

This part is about maximum independent set. So after edit question become about maximum independent set (the set of blue vertices). For leave $v$ it is easy to see that there is maximum independent set $I_v$ that contains $v$. Really if some maximum independent set $I'$ doesn't contain $v$ than it should contain the only neighbor $u$ of $v$ because otherwise it is not maximal and therefore can not be maximum. Then $I_v = (I' \setminus \{\,u\,\}) \cup \{\,v\,\}$. Also if $\deg v = 0$ then $v$ obviously should be in each maximum independent set.
If DP is the only acceptable way then let's do the following. Do depth-first search (so the stack is required anyway). For each vertex $v$ compute the number of blue vertices in subtree of $v$ if $v$ is blue (number $f_b(v)$) and if $v$ is red (number $f_r(v)$). It is possible to compute it after computing for all children in the following way: $$f_b(v) = 1 + \sum_{u \in N^+(v)} f_r(u),\\ f_r(v) = \sum_{u \in N^+(v)} \max\{\,f_r(u), f_b(u)\,\}.$$ This way also gives linear time.
• Though you probably want $f_r(v) = \sum_u \max\{f_r(u), f_b(u)\}$, instead. – Misha Lavrov May 19 '17 at 17:32