The k-color problem on an undirected graph G = (N, A) is defined as follows: Color all the nodes…
The k-color problem on an undirected graph G = (N, A) is defined as follows: Color all the nodes in N using at most k colors so that for every arc (i, j) E A, nodes i and j have a different color.
(a) Given a world map, we want to color countries using at most k colors so that the countries having common boundaries have a different color. Show how to formulate this problem as a k-color problem.
(b) Show that a graph is bipartite if and only if it is 2-colorable (i.e., can be colored using at most two colors).
