4 Graph coloring (a) Let G be a graph with 5 (non-empty) independent sets, Vi, V2,.... Vs. Suppose that the subgraph induced by taking the vertices of any pair (V, V5) of the indepen- dent sets is a complete bipartite graph. What is the chromatic number of G? (b) Is the graph below 2-colorable? If so, show a proper 2-coloring. If not, explain why not, and show a proper k-coloring for the smallest possible value of k. Let G be a graph of n vertices with chromatic number x(G). Suppose that you cannot directly access G. Fortunately, you can access G via an oracle that behaves as follows. On the first call to the oracle, the oracle returns a maximum independent set of G (in the form of a list of vertices) and then deletes from G the vertices in this set. On the second call to the oracle, the oracle returns the largest independent set in the remaining graph and then deletes these vertices from the graph as well. This process continues upon each successive call to the oracle. If you only wish to color n/2 vertices, what is the maximum number of times you must call the oracle in the worst case. Explain why this is the maximum number of calls needed. 4 Graph coloring (a) Let G be a graph with 5 (non-empty) independent sets, Vi, V2,.... Vs. Suppose that the subgraph induced by taking the vertices of any pair (V, V5) of the indepen- dent sets is a complete bipartite graph. What is the chromatic number of G? (b) Is the graph below 2-colorable? If so, show a proper 2-coloring. If not, explain why not, and show a proper k-coloring for the smallest possible value of k. Let G be a graph of n vertices with chromatic number x(G). Suppose that you cannot directly access G. Fortunately, you can access G via an oracle that behaves as follows. On the first call to the oracle, the oracle returns a maximum independent set of G (in the form of a list of vertices) and then deletes from G the vertices in this set. On the second call to the oracle, the oracle returns the largest independent set in the remaining graph and then deletes these vertices from the graph as well. This process continues upon each successive call to the oracle. If you only wish to color n/2 vertices, what is the maximum number of times you must call the oracle in the worst case. Explain why this is the maximum number of calls needed