A two-coloring of an undirected graph G is a way of assigning each vertex one of two colors, say red and blue, so that no two adjacent vertices have the same color. Put another way, to two-color a graph, you get two buckets of paint, one blue and one red. You must paint each vertex either blue or red. When you are done, it must be the case that no two red vertices are adjacent to one another and no two blue vertices are adjacent to one another.
Some graphs can be colored in that way and some cannot.
Describe an efficient algorithm that takes a connected undirected graph G and determines whether it is possible to find a two-coloring of G. The answer is yes or no.
Suppose that the coin changing problem is solved by the standard greedy algorithm, where the coin values are 1, 4, 7 and 11. Show that the greedy algorithm does not always find the fewest coins to yield a given amount of change.
Suppose that you are given a list of n open intervals (a1, b1), (a2, b2), ..., (an, bn). Your goal is to determine if it is possible to color each interval one of two colors, red or blue, in such a way that no two overlapping intervals have the same color. Describe an efficient algorithm to do that.