(Vertex coloring and exam scheduling) What is the smallest

Chapter 23, Problem 23.8

(choose chapter or problem)

(Vertex coloring and exam scheduling) What is the smallest number of exam periods for six subjects a, b, c, d, e, t if some of the students simultaneously take a, b, t, some c, d, e, some a, c, e, and some c, e? Solve this as follows. Sketch a graph with six vertices a, ... , t and join vertices if they represent subjects simultaneously taken by some students. Color the vertices so that adjacent vertices receive different colors. (Use numbers L 2, ... instead of actual colors if you want) What is the minimum number of colors you need? For any graph G, this minimum number is called the (vertex) chromatic number Xv(G). Why is this the answer to the problem? Write down a possible schedule.