Mastering Graph Colouring and Scheduling for A-Level Computer Science

Introduction to Graph Theory in Computing

In the world of A-Level Computer Science, graph theory is far more than just drawing dots and lines. It is a fundamental framework for modelling real-world constraints. One of the most elegant and practical applications of this theory is graph colouring. Whether you are designing a compiler to allocate CPU registers or creating a timetable for a school, graph colouring provides the mathematical rigour needed to solve resource conflict problems efficiently.

By the end of this article, you will understand how to represent scheduling conflicts as graphs, identify the chromatic number, and apply these techniques to exam-style problems. Mastering this topic is essential, as it bridges the gap between abstract graph theory and the practical algorithmic thinking required for your assessments.

Understanding Graph Colouring

Graph colouring is the process of assigning a label (a 'colour') to each vertex of a graph such that no two adjacent vertices share the same colour. The primary goal is usually to find the minimum number of colours required to satisfy this condition. This minimum value is known as the chromatic number, denoted by $\chi(G)$.

If two vertices are connected by an edge, they are in conflict. In a scheduling context, this means they cannot occur at the same time. By colouring the graph, we are effectively grouping non-conflicting tasks together, where each colour represents a unique time slot or resource.

The Chromatic Number and Scheduling

To solve a scheduling problem, we first construct a graph where each vertex represents a task (e.g., a lesson or a job). An edge is drawn between two vertices if those tasks cannot be performed simultaneously. The chromatic number $\chi(G)$ tells us the absolute minimum number of time slots required to complete all tasks without conflict.

Worked Example 1: The Exam Timetable

Imagine four subjects: Maths (M), Physics (P), Chemistry (C), and Biology (B). The conflicts are: M-P, M-C, P-C, and C-B.

1. Draw the vertices: M, P, C, B.
2. Add edges: (M,P), (M,C), (P,C), (C,B).
3. Assign colours:
   • Colour 1: M
   • Colour 2: P (cannot be 1 because of edge M-P)
   • Colour 3: C (cannot be 1 or 2 because of edges M-C and P-C)
   • Colour 1: B (can be 1 because B is only connected to C, which is colour 3)

Result: We used 3 colours. Thus, $\chi(G) = 3$. We need 3 time slots.

Algorithmic Approaches: The Greedy Algorithm

While finding the exact chromatic number for large, complex graphs is computationally expensive (NP-hard), we often use heuristics like the Greedy Colouring Algorithm. This algorithm does not guarantee the minimum number of colours, but it provides a valid colouring quickly.

The Greedy Algorithm Steps:

1. Order the vertices in a sequence.
2. For each vertex in the sequence, assign the lowest-numbered colour that has not been used by any of its already-coloured neighbours.

Worked Example 2: Applying Greedy Colouring

Consider a graph with vertices A, B, C, D, E. Let the order be A, B, C, D, E.

• A: Assign Colour 1.
• B: Adjacent to A? Yes. Assign Colour 2.
• C: Adjacent to A and B? Yes. Assign Colour 3.
• D: Adjacent to C? Yes. Assign Colour 1.
• E: Adjacent to D? Yes. Assign Colour 2.

This systematic approach ensures we never violate the adjacency rule, even if we don't achieve the absolute minimum number of colours.

Register Allocation in Compilers

One of the most famous applications of graph colouring in computer science is register allocation. CPUs have a limited number of high-speed registers. When a compiler translates high-level code into machine code, it must decide which variables to keep in registers and which to store in slower memory.

Variables that are 'live' at the same time cannot share the same register. By creating an interference graph where vertices are variables and edges represent overlapping lifetimes, the compiler uses graph colouring to assign registers. If the chromatic number exceeds the number of available registers, the compiler 'spills' variables to memory.

Common Mistakes

1. Confusing Edges and Vertices: Always remember that vertices are the tasks/items, and edges represent the constraints/conflicts. Never colour the edges unless specifically asked for edge-colouring.
2. Assuming Greedy is Optimal: Students often assume the Greedy Algorithm always finds the chromatic number. It does not; it only finds a valid colouring. Always double-check if you can reduce the number of colours used.
3. Ignoring Indirect Conflicts: In complex graphs, ensure you check all neighbours of a vertex before assigning a colour, not just the ones you have already processed.

Frequently Asked Questions

What is the difference between vertex and edge colouring? Vertex colouring assigns colours to nodes so no two connected nodes share a colour. Edge colouring assigns colours to edges so no two edges sharing a vertex have the same colour.

Is graph colouring always solvable? Yes, for any finite graph, you can always find a valid colouring by assigning a unique colour to every single vertex, though this is rarely the most efficient solution.

Why is graph colouring considered 'hard'? Finding the absolute minimum number of colours (the chromatic number) for very large graphs is an NP-hard problem, meaning no efficient algorithm is known to solve it perfectly in polynomial time.

Conclusion

Graph colouring is a powerful tool that transforms abstract constraints into manageable, logical structures. By understanding how to map conflicts to vertices and edges, you can solve complex scheduling and resource allocation problems with ease.

Ready to see these concepts in motion? Head over to MathInstructor AI to generate a free, narrated animated lesson that visualises these graph colouring algorithms step-by-step.