Chapter 5, Problem 35RE

Scheduling A company has scheduled a retreat at a hotel resort. It needs to hold meetings the first day there, and several conference rooms are available. Some employees must attend more than one meeting, however, so the meetings cannot all be scheduled at the same time. An "X" in the table below indicates that at least one employee must attend both of the corresponding meetings, and so those two meetings must be held at different times. Draw a graph in which each vertex represents a meeting, and an edge joins two vertices if the corresponding meetings require the attendance of the same employee. Then use graph coloring to design a meeting schedule that uses the minimum number of time slots.