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.
Solution. The idea is to start with an arbitrary vertex v, and to color it blue. Then vertices that are adjacent to v must be painted red. Vertices to those red vertices must be blue, etc.
More precisely, start with all vertices of G unpainted. Choose an arbitrary vertex v of graph G and run paint(G, blue, v), where function paint is described below. Function otherColor(c) is defined by otherColor(blue) = red and otherColor(red) = blue. I assume that, given a vertex u of G, there is an efficient way to get the vertices that are adjacent to u.
paint(G, c, v)
If vertex v is already painted color c, return true.
If vertex v is already painted otherColor(c), return false.
Paint v color c.
For each vertex u adjacent to v do
if paint(G, otherColor(c), u) is false, return false
return true
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.
Solution. Make 14 cents. The greedy algorithm selects 11 + 1 + 1 + 1. But 14 cents can be made as 7 + 7.
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.
Solution. Create an undirected graph whose vertices are the intervals, with an edge between two vertices if the corresponding intevals overlap. Now run the two-coloring algorithm.