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

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.

Related Book For answer-question

Advanced Engineering Mathematics

10th edition

Authors: Erwin Kreyszig

ISBN: 978-0470458365