From Course Conflicts to a Graph
Exam timetabling involves two different questions: which exams can happen at the same time, and how many time slots are needed? A graph makes the first question explicit. It records pairs of courses whose exams cannot run simultaneously, while a coloring assigns those courses to slots. This model gives a precise meaning to a valid timetable and a way to reason about whether fewer slots could suffice.
Assume there are finitely many courses, each course has one exam, and all exams have the same duration. In this tutorial, the only restriction is that two courses with at least one student in common must not have exams in the same slot. Other restrictions, such as room capacities, instructor availability, or unequal exam durations, are not included unless separately encoded.
A proper coloring of a graph assigns a color to every vertex so that the endpoints of each edge have different colors. The chromatic number \(\chi(G)\) is the smallest number of colors in any proper coloring of \(G\). In a timetable, colors represent time slots. For a nonempty graph with no edges, \(\chi(G)=1\); for the graph with no vertices, we use \(\chi(G)=0\).
Why Coloring Is Exactly Timetabling
Proof. Let \(G\) be the conflict graph. Given a valid timetable, assign each course the color corresponding to its exam slot. If two vertices are adjacent, their courses share a student. A valid timetable cannot place those exams in the same slot, so adjacent vertices receive different colors. Thus the assignment is a proper coloring.
Conversely, given a proper coloring, schedule each course in the slot corresponding to its color. Whenever two courses share a student, their vertices are adjacent, so the coloring assigns them different colors. Therefore no student has two exams in the same slot, and the timetable is valid. These two constructions use the same set of slots and colors, so minimizing one is exactly minimizing the other. If there are no courses, the empty timetable uses zero slots, agreeing with \(\chi(G)=0\). \(\square\)
The theorem translates the scheduling question into a graph invariant. It does not say that every graph-coloring method immediately finds an optimal timetable; it says that the optimum, when known, is precisely \(\chi(G)\). A valid coloring with \(r\) colors proves that \(r\) slots suffice. To prove that fewer cannot suffice, a lower bound is also needed.
Proof. A clique is a set of vertices in which every two distinct vertices are adjacent. Therefore every two courses represented by vertices in a clique conflict with one another. In a valid timetable, no two of these courses can share a slot. They require distinct slots, so a clique of size \(q\) requires at least \(q\) slots. Taking a clique of largest size gives \(\chi(G)\geq\omega(G)\). This also holds for the empty graph under the conventions \(\chi(G)=\omega(G)=0\). \(\square\)
Worked Timetables and Lower Bounds
Worked Example: Two Groups of Three Mutually Conflicting Courses
Suppose the courses are \(A,B,C,D,E,F\). Let \(G\) have vertex set \(V(G)=\{A,B,C,D,E,F\}\) and edge set \(E(G)=\{AB,AC,BC,CD,DE,DF,EF\}\). Thus \(A,B,C\) are pairwise conflicting, \(D,E,F\) are pairwise conflicting, and the only conflict between the two groups is \(CD\).
Assign slots by the colors \(1,2,3\): give \(A,D\) color \(1\), \(B,E\) color \(2\), and \(C,F\) color \(3\). Check every edge: \(AB\) has colors \(1,2\); \(AC\) has \(1,3\); \(BC\) has \(2,3\); \(CD\) has \(3,1\); \(DE\) has \(1,2\); \(DF\) has \(1,3\); and \(EF\) has \(2,3\). Every conflict is between different slots, so this is a valid three-slot timetable.
The vertices \(A,B,C\) form a clique of size \(3\), so the proposition shows that at least \(3\) slots are necessary. The displayed coloring uses \(3\), hence \(\chi(G)=3\) and the timetable is optimal.
Check: the edge list has \(7\) conflicts. The three edges \(AB,AC,BC\) are all checked, the four remaining listed edges \(CD,DE,DF,EF\) are all checked, and each has endpoints with different assigned colors. The triangle \(ABC\) independently certifies the lower bound of \(3\).
Worked Example: An Odd Cycle Needs Three Slots
Let five courses be \(A,B,C,D,E\), with \(V(G)=\{A,B,C,D,E\}\) and \(E(G)=\{AB,BC,CD,DE,EA\}\). The conflict graph is the cycle \(C_5\). Use the order \(A,B,C,D,E\), assigning each course the smallest positive color not already assigned to one of its earlier neighbors.
First, \(A\) has no earlier neighbors, so it receives color \(1\). Vertex \(B\) is adjacent to \(A\), so it receives color \(2\). Vertex \(C\) is adjacent among earlier vertices only to \(B\), so color \(1\) is available and \(C\) receives color \(1\). Vertex \(D\) is adjacent among earlier vertices only to \(C\), so it receives color \(2\). Finally, \(E\) is adjacent to both \(D\) and \(A\), which have colors \(2\) and \(1\). It therefore receives color \(3\).
The resulting timetable is slot \(1:\{A,C\}\), slot \(2:\{B,D\}\), and slot \(3:\{E\}\). Checking the edge list in order gives \(AB:1\ne2\), \(BC:2\ne1\), \(CD:1\ne2\), \(DE:2\ne3\), and \(EA:3\ne1\). Thus three slots suffice.
To see why two cannot suffice, suppose \(A\) receives one of two colors. The edges \(AB,BC,CD,DE\) force the colors to alternate along the path \(A,B,C,D,E\). Since there are four edges in that path, \(E\) must receive the same color as \(A\). But \(EA\) is an edge, so its endpoints must have different colors. This contradiction rules out a two-coloring. Hence \(\chi(G)=3\).
Check: the five listed conflicts have endpoint colors \(1,2\); \(2,1\); \(1,2\); \(2,3\); and \(3,1\), respectively. The alternating-color argument proves that no assignment using only two slots can pass that same edge constraint.
A Greedy Method and Its Guarantee
A simple way to construct a timetable is the greedy coloring rule. Choose an ordering of the courses, then process them one at a time. Give the current course the smallest positive-numbered slot not used by any of its already processed conflicting courses. The rule always produces a valid coloring: when a vertex is assigned, it avoids the colors of all earlier neighbors, and any later neighbor will in turn avoid its color.
Proof. Fix any ordering of the vertices and process them by the greedy rule. Consider a vertex \(v\) when it is processed. It has at most \(\deg(v)\) earlier neighbors, so at most \(\deg(v)\) colors are forbidden by those neighbors. Since \(\deg(v)\leq\Delta(G)\), at most \(\Delta(G)\) colors are forbidden. Among the \(\Delta(G)+1\) colors \(1,\ldots,\Delta(G)+1\), at least one is not forbidden, and the greedy rule assigns an available color. This holds at every step, so the entire coloring uses at most \(\Delta(G)+1\) colors. The graph is nonempty, making \(\Delta(G)\) defined. \(\square\)
This is a guarantee on the number of slots the rule will use, not a guarantee that the result is optimal. The following example shows why the order matters.
Worked Example: A Poor Ordering Uses an Extra Slot
Let \(G\) have vertex set \(V(G)=\{v_1,v_2,v_3,v_4\}\) and edge set \(E(G)=\{v_1v_2,v_2v_3,v_3v_4\}\). This is a path on four vertices. Apply the greedy rule in the order \(v_1,v_4,v_2,v_3\).
The first vertex \(v_1\) has no earlier neighbor, so gets color \(1\). Vertex \(v_4\) is not adjacent to \(v_1\), so it also gets color \(1\). Vertex \(v_2\) is adjacent to the earlier vertex \(v_1\) with color \(1\), so it gets color \(2\). Vertex \(v_3\) is adjacent to the earlier vertices \(v_2\) and \(v_4\), whose colors are \(2\) and \(1\), so it gets color \(3\).
The algorithm has produced colors \(1,2,3,1\) on \(v_1,v_2,v_3,v_4\). Checking the three edges gives \(v_1v_2:1\ne2\), \(v_2v_3:2\ne3\), and \(v_3v_4:3\ne1\). It is a valid three-slot timetable.
However, two slots suffice: assign color \(1\) to \(v_1,v_3\) and color \(2\) to \(v_2,v_4\). Each of the three edges joins different colors, so this is a valid coloring. Since \(v_1v_2\) is an edge, at least two colors are necessary. Therefore \(\chi(G)=2\), and the greedy coloring in the chosen order is not optimal.
Check: the degrees are \(1,2,2,1\), so \(\Delta(G)=2\) and the theorem guarantees at most \(2+1=3\) colors. The computed greedy result uses \(3\), within the guarantee, while the explicit two-color schedule proves the optimum is \(2\).
Interpreting and Using the Model
A color class is the set of courses assigned to one slot. Because a proper coloring gives no edge within a color class, no two courses in that slot share a student. Equivalently, each color class is an independent set: a set of vertices with no edges between any pair. Thus a timetable partitions the courses into independent sets, and the smallest number of such sets is \(\chi(G)\).
In practice, a useful workflow is to construct the conflict graph, produce a coloring, and then seek a lower bound. A large clique is a direct certificate that many slots are unavoidable. If the coloring uses exactly as many colors as the clique size, optimality follows without checking every possible timetable. If the bounds do not match, the coloring still proves that its number of slots is sufficient, but does not by itself establish minimality.
The conflict graph is only as accurate as its edge definition. If a student is enrolled in three courses, all three pairs must be connected, since each pair of exams would conflict. Conversely, an edge should not be added merely because two courses seem similar: under this model it means that at least one student takes both. Additional real-world constraints may require additional modeling, and a coloring optimal for the student-conflict graph need not be an optimal schedule once those other constraints are imposed.
Common Pitfall: Treating a Greedy Schedule as Optimal
A common error is to observe that a particular greedy order uses three colors and conclude that three slots are necessary. In the path example, the greedy calculation \(v_1=1,\ v_4=1,\ v_2=2,\ v_3=3\) is valid, but it only proves that three slots suffice. It does not prove that two slots are impossible. The corrected argument supplies the coloring \(v_1,v_3\) in one slot and \(v_2,v_4\) in another; the edge check verifies validity, and the edge \(v_1v_2\) proves that one slot cannot suffice. Thus \(\chi(G)=2\), despite the three-color greedy output.
Keep the roles of the two kinds of evidence separate: a coloring is an upper bound on the minimum number of slots, while a clique is a lower bound. Matching bounds certify an optimal timetable.
Check Your Understanding
For each question, state the relevant conflict or coloring condition explicitly.
- Suppose \(G\) has vertices \(\{A,B,C,D\}\) and edges \(\{AB,BC,CD\}\). Give a two-slot timetable and explain why one slot cannot work.
- Three courses are pairwise conflicting. What lower bound does this give on the number of slots, and which graph structure supplies it?
- Explain why every color class in a proper coloring is an independent set of courses.
- A greedy ordering uses four colors. What has been proved about the minimum number of slots, and what has not been proved?
- Why must three courses whose exams share a student pairwise form a triangle in the conflict graph?