1. Given a graph G =(V, E) a k-coloring of G is a labeling of the vertices with the colors 41,02,..., Gesuch that for every edge (u, v) the color of u is different from the color of v. (a) Give a linear time dynamic programming algorithm that creates a 3-coloring for a tree such that the maximum number of nodes are colored . Justify your