Difficulty: Intermediate | Prerequisites: Basic graph theory (vertices, edges, adjacency)
Vertex coloring is about assigning labels ("colours") to the vertices of a graph so that no two adjacent vertices share the same colour. It is one of the foundational problems in graph theory, with direct applications in scheduling, register allocation in compilers, map colouring, and frequency assignment in telecommunications. You should already know what a graph is, what adjacency means, and ideally have covered spanning trees (the companion topic on this worksheet).
Vertex coloring assigns colours to vertices so that no edge connects two vertices of the same colour. The chromatic number is the smallest number of colours needed to achieve this. The Greedy Coloring Algorithm works through vertices in a fixed order, assigning the lowest-numbered colour that does not conflict with already-coloured neighbours.
Vertex coloring (graph coloring)
An assignment of colours (or labels) to the vertices of a graph such that no two adjacent vertices receive the same colour. In simple terms, you are painting dots so that connected dots are always different colours.
Proper coloring
A vertex coloring where the rule (no two adjacent vertices share a colour) is satisfied everywhere. If even one edge connects two same-colour vertices, the coloring is not proper.
Chromatic number (χ)
The minimum number of colours required to properly colour a graph. In simple terms, the fewest crayons you can get away with. A graph with chromatic number 3 cannot be properly coloured with 2 colours but can with 3.
k-colorable
A graph is k-colorable if it can be properly coloured using at most k colours.
Greedy Coloring Algorithm
An algorithm that processes vertices in a predetermined order and assigns each vertex the lowest-numbered colour not already used by any of its neighbours. Think of it as: "Look at what my neighbours are wearing, then pick the first colour they are not."
Adjacent vertices
Two vertices connected by an edge. Adjacency is the constraint that drives coloring: adjacent vertices must differ in colour.
Steps:
Fix an ordering of vertices (the problem will tell you where to start, e.g. "begin at vertex A").
Assign the first vertex colour #1.
Move to the next vertex in order. Look at all of its already-coloured neighbours.
Assign it the lowest-numbered colour not used by any neighbour.
Repeat until every vertex is coloured.
Worked example (from the worksheet, Question 9):
Graph with vertices A through K. Starting at A with colour #1.
A: colour #1 (no neighbours coloured yet).
B: adjacent to A (colour #1), so B gets colour #2.
C: check neighbours. Assign the lowest available colour.
Continue through D, E, F, G, H, I, J, K, each time scanning coloured neighbours and picking the first free colour.
The worksheet solution used 4 colours. The greedy algorithm does not always produce the optimal (minimum) number of colours; the result depends on the vertex ordering.
The chromatic number χ(G) of a graph G is the smallest k for which G is k-colorable.
To show that χ(G) = k, you need two things:
A valid coloring using k colours (proves χ ≤ k).
An argument that k - 1 colours are not enough (proves χ ≥ k). Typically you find a clique (complete subgraph) of size k, or show that any (k - 1)-coloring fails.
Constructing a graph with a given chromatic number (Question 11):
To build a graph with 6 vertices and chromatic number 3, include at least one triangle (3-clique) so that 2 colours are insufficient, but arrange the remaining edges so that 3 colours suffice. The worksheet shows a graph where three colours are needed and sufficient.
Sometimes you are asked to colour a graph with a given number of colours (e.g. "use 3 colours") with no prescribed vertex order. The constraint is simply: no two adjacent vertices share a colour.
Strategy: start with high-degree vertices (they have the most constraints), assign colours, then fill in the rest. Check every edge to confirm the colouring is proper.
Vertex coloring solves scheduling conflicts. In the worksheet's committee problem:
Each committee is a vertex.
An edge connects two committees that share a member (and therefore cannot meet at the same time).
Each colour represents a time slot.
The chromatic number tells you the minimum number of time slots needed so that no member has two meetings at once.
The adjacency table tells you which committees conflict. Build the graph from the table, then colour it. The worksheet graph had chromatic number 3, meaning 3 time slots are the minimum.
This same principle applies to exam scheduling (no student should have two exams at the same time), class timetabling, and frequency assignment in wireless networks (adjacent transmitters must use different frequencies).
Students often assume the Greedy Coloring Algorithm always finds the chromatic number. It does not. The result depends on the vertex ordering. A different ordering can use more colours than necessary.
Confusing "uses k colours" with "chromatic number is k": just because you found a valid 4-colouring does not mean the chromatic number is 4. It could be 3 or even 2. The chromatic number is the minimum.
Thinking that a graph with a triangle must have chromatic number exactly 3. A triangle means χ ≥ 3, but the rest of the graph might force χ higher.
Forgetting to check every edge when verifying a colouring. One overlooked edge between two same-colour vertices makes the entire colouring invalid.
⚠️ Expect to be asked to apply the Greedy Coloring Algorithm step by step, starting from a specified vertex and using a specified colour numbering.
⚠️ You may be asked to colour a graph using exactly k colours, or to determine the chromatic number and justify your answer (show both a valid k-colouring and why k - 1 fails).
⚠️ The scheduling application (committees, exams, classes) is a favourite exam topic. You must be able to build the conflict graph from a table and interpret the chromatic number as "minimum time slots."
⚠️ Constructing a graph with a given chromatic number (e.g. 6 vertices, χ = 3) tests whether you understand the concept beyond just applying an algorithm.
True or False: In a proper vertex coloring, two adjacent vertices may share the same colour.
Fill in the blank: The chromatic number of a graph is the ______ number of colours needed for a proper colouring.
True or False: The Greedy Coloring Algorithm always produces the optimal (minimum) number of colours.
True or False: A complete graph on 5 vertices (K₅) has chromatic number 5.
Fill in the blank: In a scheduling application, each colour in a vertex colouring represents a ______.
Answers: 1. False. 2. minimum. 3. False (it depends on vertex ordering). 4. True. 5. time slot.
Q: What is the chromatic number of a cycle graph with 5 vertices (C₅)?
A: 3. An odd cycle cannot be 2-coloured (you will always end up with two adjacent vertices forced into the same colour), but 3 colours suffice.
Q: You apply the Greedy Coloring Algorithm to a graph starting at vertex A and use 4 colours. Your classmate starts at vertex D and uses only 3 colours. Who found the chromatic number?
A: Your classmate's result (3) is an upper bound, as is yours (4). The chromatic number is at most 3, because a valid 3-colouring exists. It could be exactly 3, or it could be lower. To confirm χ = 3, you would also need to show that 2 colours are not enough.
Q: Six committees share members as follows: A-B share a member, A-D share a member, B-C share a member, D-E share a member, D-F share a member, E-F share a member. What is the minimum number of time slots needed?
A: Build the conflict graph (edges: A-B, A-D, B-C, D-E, D-F, E-F). The triangle D-E-F forces at least 3 colours. Checking: colour D = 1, E = 2, F = 3, A = 2 (adjacent to B and D, not 1, not yet constrained by 2, but wait, A-D means A ≠ 1, A-B means A ≠ B's colour), B = 1 (adjacent to A and C), C = 2 (adjacent to B only). Three time slots suffice, so χ = 3.
Q: Explain what the chromatic number represents in a real-world scheduling problem.
A: The chromatic number is the minimum number of non-overlapping time slots required so that no person is double-booked. Each colour corresponds to a time slot, and the coloring constraint ensures conflicting events (those sharing participants) land in different slots.
Q: Can a tree (with at least one edge) always be 2-coloured? Why?
A: Yes. A tree has no cycles, so you can alternate two colours along every branch. Start at the root with colour 1, assign colour 2 to all its children, colour 1 to their children, and so on. No two adjacent vertices will share a colour.
Vertex coloring is the natural companion to spanning trees on this worksheet. Both operate on the same graph structures: spanning trees select edges, while vertex coloring assigns labels to vertices. A tree (and therefore any spanning tree) is always 2-colourable, which links the two topics directly.
The scheduling application of vertex coloring connects to operations research and combinatorial optimisation. If you take a course in those areas, you will see graph coloring reappear in resource allocation, timetabling, and constraint satisfaction problems.
The Four Colour Theorem (every planar graph can be coloured with at most 4 colours) is one of the most famous results in mathematics. It was proved in 1976 with the aid of a computer, making it one of the first major theorems to rely on computational verification.
Vertex coloring, graph coloring, chromatic number, proper coloring, greedy coloring algorithm, k-colorable, scheduling problem, exam timetabling, map coloring, Four Colour Theorem, adjacent vertices, conflict graph, clique, complete graph, CS 101, discrete mathematics, combinatorics, constraint satisfaction, frequency assignment