1. Suppose you are responsible for scheduling the classes at a high school. Each class has:
- A grade level, one of the numbers 9, 10, 11, 12
- Whether it is a remedial class, a regular course, or an honors class
- An instructor
There are 100 classes to schedule, and five different periods that they may be scheduled into. No two classes with the same instructor may be scheduled for the same period. Also, no two honors classes for the same grade may be scheduled for the same period, and no two remedial classes for the same grade may be scheduled for the same period. Describe how to represent this as a graph coloring problem. What do the vertices, edges, and colors of the problem represent? Which pairs of vertices are connected by edges?


2. Suppose that you are going to use the greedy coloring algorithm to color the vertices of a tree, aiming to use as few colors as possible. Would it be better, for this algorithm, to order the tree vertices in preorder or in postorder? Explain why.


3. Write a fragment of code (in C, C++, Java, Python, or a similar language) with four variables x, y, z, and w such that the conflict graph of these variables is a single cycle. (Since this is not a chordal graph, you will need to break some of the assumptions from the lecture that cause conflict graphs to be chordal.)


4* (265 only). Let G be a graph with six vertices, labeled by the letters a, b, c, d, e, and f, such that the maximal cliques of G are {a, b, c}, {a, b, d}, {a, e, c}, and {f, b, c}.
(a) Is this graph a chordal graph? Explain why or why not.
(b) Is this graph an interval graph? Explain why or why not.