Discrete mathematics and graph theory · Maths EE idea · Solid

Colouring graphs to build timetables

A research question to start from

How can graph colouring schedule exams without clashes, and how close does a greedy algorithm come to the minimum number of sessions?

A starting point, not your question: change the case, the comparison or the limit until it is yours. The research-question builder helps you check it.

Why it works as a maths EE

Theory (bounds on the chromatic number) and an algorithm evaluated against it.

Mathematics you would need

Chromatic number
Greedy colouring and ordering
Bounds such as Brooks' theorem
Worst-case examples

Much of this goes beyond the DP course. That is expected in a maths EE, but you must understand and explain everything you use.

One possible line of attack

Model a timetable you design as a graph.
Prove greedy uses at most Δ + 1 colours.
Find orderings that make greedy do badly and discuss.

Scope and difficulty

Solid. Solid.

Pitfalls

Real school data with privacy issues.
No proofs of bounds.

Where to start reading

Search a library catalogue or a university's open lecture notes for: greedy colouring bound Delta+1; Welsh-Powell algorithm; Brooks theorem. Prefer textbooks, lecture notes and journal articles to a single website, and cite everything you use (how to reference a maths EE).

Make it your EE

Plan this EEOpens the free EE planner with this question as a starting point. Sharpen the questionSix quick checks for a focused research question. Self-check a draftCheck a section against each criterion, free.