Chapter 23, PROBLEM SET 23.8 #19

What is the smallest number of exam periods for six subjects α, b, c, d, e, f if some of the students simultaneously take α, b, f, some c, d, e, some α, c, e, and some c, e? Solve this as follows. Sketch a graph with six vertices α, · · ·, f and join vertices if they represent subjects simultaneously taken by some students. Color the vertices so that adjacent vertices receive different colors. (Use numbers 1, 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 Χ_{v}(G). Why is this the answer to the problem? Write down a possible schedule.

PROBLEM SET 23.2:

PROBLEM SET 23.4:

PROBLEM SET 23.5:

PROBLEM SET 23.6:

PROBLEM SET 23.7:

PROBLEM SET 23.8: