Convert class schedule problem to coloring problem

combinatoricsgraph theory

I am working on Problem 16 of the exercise www.rellek.net/book/s_graphs_exercises.html

  1. A school is preparing the schedule of classes for the next academic year. They are concerned about scheduling calculus, physics, English, statistics, economics, chemistry, and German classes, planning to offer a single section of each one. Below are the lists of courses that each of six students must take in order to successfully graduate. Determine the smallest number of class periods that can be used to schedule these courses if each student can take at most one course per class period. Explain why fewer class periods cannot be used.
    Student
    Courses
    1
    Chemistry, Physics, Economics
    2
    English, German, Statistics
    3
    Statistics, Calculus, German
    4
    Chemistry, Physics
    5
    English, Chemistry
    6
    Chemistry, Economics

Is there a way to convert this problem to a graph coloring one?

Best Answer

Consider a graph that has 7 vertices for each for the 7 classes. Put an edge between two vertices if there is student that needs to take both of the corresponding classes. For example, there must be an edge between the vertex corresponding to German and the one corresponding Calculus since student 3 needs to take both. Chromatic number of this graph (the minimum number of colors you need to color the vertices so that adjacent vertices have different color) is the minimum number of periods.

Related Question