Skip to content
Tutorials Center
My learning

Topics

Lesson 32 of 36 ยท Applications

Scheduling and Timetabling with Coloring

Apply graph coloring to real scheduling: build conflict graphs for exam timetables, add capacity limits, color interval graphs optimally and see register allocation as coloring.

Colorings sound abstract until you have to schedule 40 exams in as few time slots as possible so that no student has two exams at once. Then the connection is immediate: exams are vertices, an edge joins two exams that share a student, and a time slot is a color. A proper coloring is a clash-free timetable, and the chromatic number is the minimum number of slots. This lesson turns the theory from coloring basics and greedy coloring into working schedulers.

The conflict graph recipe

Almost every scheduling-by-coloring problem follows the same three steps:

  1. Items to schedule become vertices (exams, classes, meetings, radio transmitters, compiler variables).
  2. Conflicts (cannot share a resource or time) become edges.
  3. Resources (time slots, rooms, frequencies, registers) become colors.

The result is a conflict graph, and its color classes are independent sets: groups of items that can safely run together. If extra requirements appear (room capacity, fixed slots, preferences), they become constraints on the coloring.

flowchart LR
    S["Student enrollments"] --> G["Conflict graph"]
    G --> C["Color with DSATUR"]
    C --> T["Timetable: one color = one slot"]
    T --> V["Verify no student has a clash"]

The pipeline from raw data to a verified timetable.

Exam timetabling

Given each student's list of exams, two exams conflict when at least one student takes both. We build the conflict graph, color it with DSATUR, and then verify the timetable directly against the enrollment data, since the check is easy and catches modeling bugs.

Python Exam timetable via DSATUR and an independent verification

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The number of slots is an upper bound on the optimum. For a lower bound, find a clique: a set of exams that pairwise conflict needs one slot each. If the clique size equals the number of slots used, the timetable is provably optimal. In the example above, Math, Physics, Chem and Art pairwise share a student (s1, s3, s4, s5), so four slots is the true minimum.

Adding capacity constraints

Real timetables have limits: only so many seats are available in a slot. A capacity-constrained coloring limits the total size of each color class. Greedy handles this naturally: when choosing a color for a vertex, accept only a color that is neither used by a neighbor nor full. If no color qualifies, open a new slot.

Python Greedy coloring with a seat limit per slot

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Tightening the capacity forces more slots. It is a classic bin packing meets coloring tradeoff, and heuristics such as greedy with the right ordering are the standard practical tool because the exact problem is NP-hard.

Interval graphs: when coloring is easy

Many scheduling problems have a special structure: each item occupies a time interval, and two items conflict when their intervals overlap. The conflict graph is an interval graph, and these are always easy to color optimally. Sort the intervals by start time; give each interval the smallest color not used by an overlapping, already-colored interval. The greedy algorithm is optimal, and the number of colors equals the maximum number of intervals overlapping at any moment (the maximum clique). This is exactly the "how many meeting rooms do we need?" problem.

Interval graphs are a first example of perfect graphs, where ฯ‡(H) = ฯ‰(H) for every induced subgraph H. For perfect graphs coloring is polynomial; bipartite graphs, chordal graphs and comparability graphs are also perfect.

Python Meeting rooms: interval coloring equals maximum overlap

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Notice that the greedy rule reuses a room whose previous meeting has ended (ties at end == start do not conflict, which is why events sort end markers before start markers at equal times).

Compilers: register allocation

A compiler decides which program variable lives in which CPU register. Two variables conflict when they are live at the same time; this builds an interference graph, and coloring it with k colors assigns k registers. If the graph needs more colors than there are registers, some variables are spilled to memory. Straight-line code gives interval graphs (easy), while arbitrary control flow gives general graphs, where compilers use heuristics such as Chaitin-Briggs: repeatedly remove vertices of degree < k (they are always colorable) and push them on a stack, then color in reverse order, exactly the smallest-last idea.

Other coloring applications

  • Frequency assignment: transmitters that are close need different frequencies.
  • Sudoku: a 9-coloring of a graph with 81 vertices, where cells in the same row, column or box are adjacent and some cells are precolored.
  • Map and territory coloring: coloring the dual graph of a map (see planar graphs).
  • Register and memory-slot allocation, test scheduling, traffic-light phases.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. In exam timetabling modeled as a graph coloring, what does a color represent?

    Vertices are exams, edges join exams that share a student, and each color class is a set of exams that can safely run in the same slot.
  2. 2. How do you obtain a lower bound on the number of slots?

    Exams in a clique pairwise conflict and therefore need distinct slots, so the clique size is a lower bound.
  3. 3. How many meeting rooms does an optimal schedule need?

    Interval graphs are perfect, so the chromatic number equals the maximum clique size, which is the peak number of simultaneous meetings.
  4. 4. In a register allocator, what does it mean for a variable to be spilled?

    If the interference graph cannot be colored with k registers, some variables are placed in memory instead.

Summary

  • Scheduling problems become coloring: items are vertices, conflicts are edges, resources are colors.
  • Greedy DSATUR gives good timetables; cliques give lower bounds; always verify against the raw data.
  • Capacity limits turn coloring into a bin-packing-flavored problem that greedy heuristics handle well.
  • Interval graphs are perfect: sorting by start time and coloring greedily is optimal, and the answer is the maximum overlap.
  • Register allocation, frequency assignment and Sudoku are all colorings of a conflict graph.

Next: Network Models: Small Worlds and Scale-Free Graphs