We will take a quick sojourn into algorithms for coloring.
(a) Design a greedy (parsimonious) algorithm for coloring the vertices of a graph.
(b) Your algorithm addresses the vertices in some order. Try it out on the graph in Figure 13.13. In fact, try your algorithm with each of the vertex orderings given in Figure 13.13. Does your algorithm give the optimal coloring in each case?
(c) Design a greedy (parsimonious) algorithm for coloring the edges of a graph.
(d) Your algorithm addresses the edges in some order. Try it out on the graph in Figure 13.14. In fact, try your algorithm with each of the edge orderings given in Figure 13.14. Does your algorithm give the optimal coloring in each case?
