COMPSCI320 Chap.5 Greedy Graph Colouring and Interval Partitioning
Greedy Graph Colouring and Interval Partitioning
This chapter studies greedy colouring from the fourth tutorial. Each vertex receives the smallest colour not used by a coloured neighbour, which never needs more than the maximum degree plus one colours.
The visiting order changes the result, so the chapter shows two orders on one graph, then proves that sorting intervals by start time makes greedy colouring optimal through a clique lower bound.
A short trace in two orders shows the same graph needing three colours or two, and a lane diagram shows interval partitioning reaching the depth of the intervals.
The chapter ends with the dense subgraph heuristic, a reminder that greedy can be a fast heuristic rather than an exact method.
What this chapter covers
- 01
Proper colourings and the chromatic number
- 02
The smallest free colour rule
- 03
The maximum degree plus one bound
- 04
Why the vertex order matters
- 05
Interval graphs coloured by start time
- 06
Cliques as lower bounds
Worked example · free
Greedy colouring of a six-vertex graph in two orders
- 1Order a, f, b, c, d, e: a and f both get 1, then b and c get 2.
- 1d sees colours 2, 2 and 1 and gets 3; e sees 2 and 1 and gets 3, so three colours are used.
- 1Alphabetical order: a 1, b 2, c 2, d 1, e 1, f 2, using two colours.
- 1Any edge needs two colours, so the alphabetical run is optimal and the first run wastes one.
Key terms
- Proper Colouring
- An assignment of colours to vertices so that every edge joins two vertices of different colours.
- Chromatic Number
- The smallest number of colours that admits a proper colouring of a graph.
- Interval Graph
- A graph with one vertex per interval and an edge for every pair of intervals that overlap.
- Clique
- A set of vertices in which every pair is joined by an edge.
- Interval Partitioning
- Assigning intervals to as few groups as possible so that no group holds two overlapping intervals.
- Smallest Free Colour
- The lowest colour number not used by any already coloured neighbour of the current vertex.
- Maximum Degree
- The largest number of edges meeting at any single vertex of a graph.
Greedy Graph Colouring and Interval Partitioning FAQ
Why can greedy colouring never need more than maximum degree plus one colours?
When a vertex is coloured, at most d of its neighbours already have colours, where d is the maximum degree. So at most d colours are blocked, and one of the colours from 1 to d + 1 is always free. The rule therefore never reaches colour d + 2, whatever order the vertices are visited in.
Does a better vertex order always reach the chromatic number?
Some order always does, because colouring an optimal colouring's classes one after another reproduces it, but finding that order is as hard as colouring itself. Practical rules such as visiting high-degree vertices first often help without guarantees. For interval graphs, sorting by start time is guaranteed optimal, which is why that special case matters.
How do I prove an interval colouring is optimal?
Find a time point covered by as many intervals as the colouring uses. Those intervals overlap pairwise, forming a clique, and every colouring needs a different colour for each member. In the start-order greedy argument, an interval receiving colour k was blocked by k − 1 intervals still open at its start, which supplies exactly such a point.
Why is colouring interval graphs easier than colouring general graphs?
Intervals have a natural order by start time, and in that order every coloured neighbour of a new interval is still running when it starts. The blocked colours therefore all come from intervals sharing one point, which form a clique. That clique proves the greedy count optimal, while general graphs have no such order and colouring them is NP-hard.
Exam move
Colour one small graph under two different orders and record the counts, then compute the maximum degree bound and compare. For interval sets, sweep the start times to find the maximum depth before colouring, so you know the target in advance. Write the clique argument once in full so that you can reproduce it quickly in an exam.
As a final check, colour one interval set by finish time instead of start time and see whether the clique argument still holds, which shows why the start order matters. Finish by explaining in one sentence why the heuristic for dense subgraphs carries no optimality guarantee.
Working through Greedy Graph Colouring and Interval Partitioning in COMPSCI320? Sia is AskSia’s AI Computer Science tutor — ask any COMPSCI320 Greedy Graph Colouring and Interval Partitioning question and get a clear, step-by-step explanation grounded in how COMPSCI320 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.
