In this exercise a graph is used to help solve a

Chapter 10, Problem 47E

(choose chapter or problem)

Problem 47E

In this exercise a graph is used to help solve a scheduling problem. Twelve faculty members in a mathematics department serve on the following committees:

Undergraduate Education: Tenner, Peterson, Kashina, Cohen Graduate Education: Gatto, Yang, Cohen, Catoiu Colloquium: Sahin, McMurry, Ash Library: Cortzen, Tenner, Sahin

Hiring: Gatto, McMurry, Yang, Peterson Personnel: Yang, Wang, Cortzen

The committees must all meet during the first week of classes, but there are only three time slots available. Find a schedule that will allow all faculty members to attend the meetings of all committees on which they serve. To do this, represent each committee as the vertex of a graph, and draw an edge between two vertices if the two committees have a common member. Find a way to color the vertices using only three colors so that no two committees have the same color, and explain how to use the result to schedule the meetings.