In Example 12.17, we discussed a high school, which holds end-of-course exams in (E3) English 3, (E4) English 4, (M) Advanced Math, (C) Calculus, (W) World History, (U) U.S. History, (B) Biology, and (P) Physics. We were given a list of courses that had no students in common. We used that information to find the graph in Figure 12.63, which shows edges between exams with students in common. Use the graph we found in Example 12.17 to answer each question.

1. The graph contains a clique of size 4 formed by the vertices \(P, E 3, C\), and U. What does this tell you about the chromatic number?
2. The graph is not planar, meaning that you cannot untangle it. What does this tell you about the chromatic number?
3. Create a coloring by coloring vertex of highest degree first, coloring as many other vertices as possible each color from highest to lowest degree, then repeating this process for the remaining vertices.

4. Do you know what the minimum number of timeslots is? If so, what is it and how do you know? If not, what are the possibilities?

Transcribed Image Text:

B P E3 E4 M C U W Figure 12.97 Graph of Exams with Students in Common