6.042/18.] Mathematics for Computer Science March 3, 2005 Srini devadas and Eric Lehman Lecture notes Graph Theory II 1 Coloring Graphs Each term, the MIT Schedules Office must assign a time slot for each final exam. This is not easy, because some students are taking several classes with finals, and a student can take only one test during a particular time slot. The Schedules Office wants to avoid all conflicts, but to make the exam period as short as possible We can recast this scheduling problem as a question about coloring the vertices of a graph. Create a vertex for each course with a final exam. Put an edge between two vertices if some student is taking both courses. For example, the scheduling graph might look like this Next, identify each time slot with a color. For example, monday morning is red, Mon day afternoon is blue tuesday morning is green et Assigning an exam to a time slot is now equivalent to coloring the corresponding ver- tex. The main constraint is that adjacent vertices must get different colors; otherwise, some student has two exams at the same time. Furthermore in order to keep the exam period short, we should try to color all the vertices using as few different colors as possi ble. For our example graph, three colors suffice: blue green green6.042/18.062J Mathematics for Computer Science March 3, 2005 Srini Devadas and Eric Lehman Lecture Notes Graph Theory II 1 Coloring Graphs Each term, the MIT Schedules Office must assign a time slot for each final exam. This is not easy, because some students are taking several classes with finals, and a student can take only one test during a particular time slot. The Schedules Office wants to avoid all conflicts, but to make the exam period as short as possible. We can recast this scheduling problem as a question about coloring the vertices of a graph. Create a vertex for each course with a final exam. Put an edge between two vertices if some student is taking both courses. For example, the scheduling graph might look like this: Next, identify each time slot with a color. For example, Monday morning is red, Mon￾day afternoon is blue, Tuesday morning is green, etc. Assigning an exam to a time slot is now equivalent to coloring the corresponding ver￾tex. The main constraint is that adjacent vertices must get different colors; otherwise, some student has two exams at the same time. Furthermore, in order to keep the exam period short, we should try to color all the vertices using as few different colors as possi￾ble. For our example graph, three colors suffice: red green blue green blue