In 1852, a maths student named Francis Guthrie was colouring a map of the counties of England and noticed that he only needed four colours to ensure no two adjacent counties shared a colour. He asked his brother, who asked his professor, who asked other mathematicians. It took 124 years and eventually a computer-assisted proof to confirm: four colours are always sufficient for any map.
That's a graph colouring problem. Each county is a node. Each shared border is an edge. The question is: what's the minimum number of colours needed so that no two connected nodes share a colour?
Here it is on a real map. Estonia has 15 counties. Four colours are enough to colour every one so that no two neighbours share a colour -- including the islands, which technically could be any colour since they don't border anything on land.
Strip away the geography and the same information looks like this. Each county becomes a circle, each shared border becomes a line. The colours still work -- no two connected nodes share a colour.
You've seen this before, probably without the formal name. It turns out you've been solving it at work too.
A sprint plan is a graph
Take five tasks for a sprint. Some need the same person. Some need the same test rig. Some can't run in parallel because they touch the same service. The challenge is scheduling them across the team and across the week without conflicts.
Each task is a node. Each constraint (can't overlap, needs the same person, needs the same equipment) is an edge. The "colours" are time slots, or people, or workstations. The question is the same as Guthrie's: what's the minimum number of resources needed so that no two conflicting tasks are assigned to the same one at the same time?
In graph theory, a set of nodes where every pair is connected is called a clique. API redesign, DB fix, and Infra migration all need Alice, so every pair conflicts -- a 3-clique. Tests and ML pipeline both need Bob on Tuesday -- a 2-clique. If three tasks all need the same person, you need at least three time slots -- no reshuffling changes that. It's a hard lower bound. The Gantt chart hides this because the cross-row dependency (Infra migration needs Alice too) is invisible until you draw the graph.
This gets more interesting when your team isn't uniform. Some tasks need several people working together -- a backend engineer and a data scientist pairing on an integration, say. And each person has a specific set of skills, not all interchangeable. The graph isn't just "who's free?" -- it's "who's free AND can do this AND isn't needed simultaneously for that other thing?"
One task might need multiple workers. But one worker can only handle one task at a time -- and context switching between tasks is painful. You don't get 50% of each, you get maybe 30% of each and 40% lost to thrashing.
Most managers solve this with a whiteboard and gut feel. The good ones are doing graph colouring intuitively -- they can "see" the constraints and find a valid assignment quickly. The great ones know when to violate a constraint because they understand which edges are hard constraints and which are preferences.
This should be reassuring: finding the optimal solution to this problem is NP-complete. It's provably hard -- there's no fast algorithm that guarantees the best answer for all cases. If scheduling your sprint feels difficult, that's because it IS difficult.
The good news: you don't need optimal. Greedy heuristics -- assign the first available colour that doesn't conflict, move to the next node -- get close to optimal most of the time. This is essentially what an experienced manager does: start with the hardest-to-schedule task, assign the best available person, move on. It works. Not perfectly, but well enough. And "well enough, quickly" beats "optimal, eventually" when you have a sprint starting Monday.
What the backlog really looks like
If you've read the backlog article, you'll recognise the connection. A ticket backlog is a queue. A scheduling problem is a graph. The backlog becomes a graph problem when you start asking not just "what's next?" but "what can run in parallel, given the constraints on who's available and what depends on what?"
Most teams treat their backlog as a list -- ordered by priority, pulled from the top. This ignores the graph structure entirely. Task #3 might be lower priority than task #1, but if task #1 is blocked waiting for an external API and task #3 can be done right now by someone who's free, the list-based approach leaves capacity idle while higher-priority work sits blocked.
The north-star metric helps here too. When you can attach a value to each task (what's it worth in terms of the metric?), the problem gets richer. You're not just minimising conflicts -- you're maximising the total value of work completed in a given time window. That's operations research, and it's been studied since the 1940s. Attach the north-star metric to each node, and the graph doesn't just tell you what conflicts -- it tells you what to sacrifice. A 3-clique with tasks worth EUR 50K, EUR 200K, and EUR 5K stops being an impossible constraint. You drop the EUR 5K task and the maths resolves itself.
Now for the engineering parallel
Not an engineer? Skip to the takeaways.
If you're a software engineer, you've been relying on a graph colouring solver every time you compile code.
The compiler first converts your source to SSA (Static Single Assignment) form, where each variable is assigned exactly once. Then it needs to decide which CPU register holds each variable. Registers are fast but scarce -- a typical CPU has only a handful. Here's a function before and after the SSA transform:
fn score(base, bonus, penalty) {
gross = base + bonus
adjusted = base - penalty
if gross > adjusted {
result = gross - penalty
} else {
result = adjusted + bonus
}
return result
}fn score(base_0, bonus_0, penalty_0) {
gross_0 = base_0 + bonus_0
adjusted_0 = base_0 - penalty_0
if gross_0 > adjusted_0 {
result_1 = gross_0 - penalty_0
} else {
result_2 = adjusted_0 + bonus_0
}
result_3 = φ(result_1, result_2)
return result_3
}Each assignment creates a new numbered version: result_1, result_2. The φ (phi) function at the merge point picks whichever version the branch actually produced -- result_1 if we took the if branch, result_2 if we took the else. Key insight: result_1 and result_2 are never alive at the same time, because only one branch executes (unless you're programming a GPU, where both branches may execute simultaneously and one is masked off). No edge between them in the interference graph. They can share a register.
But this function has a harder problem. After gross_0 = base_0 + bonus_0, four variables are alive simultaneously: base_0 (still needed), bonus_0 (used in the else-branch), penalty_0 (used in both branches), and the freshly computed gross_0. With only three registers -- call them Cyan, Magenta, and Yellow -- something has to give. The allocator "spills" penalty_0 to memory: slower, but it frees a register for the variables that need one right now.
The same information as a graph: each variable is a node, and an edge means "alive at the same time." The nodes coloured cyan are in the Cyan register, magenta in the Magenta register, yellow in Yellow. Grey means spilled. base_0 and adjusted_0 share the Magenta register because one dies exactly when the other is born -- same trick as result_1 and result_2 sharing Cyan across different branches.
When the compiler runs out of colours (more simultaneously-live variables than registers), it "spills" -- moves a variable to memory temporarily, which is slow. The compiler's register allocator is doing exactly what a manager does when they run out of people: the work still happens, but it's slower because something that should have stayed close (in a register, on the team) got pushed out (to RAM, to an external contractor, to next sprint).
Modern CPUs make this even more interesting. Cores aren't all equal any more. Intel's recent chips have Performance cores and Efficiency cores -- big fast cores for heavy work, small slow cores for background tasks. ARM's big.LITTLE does the same. NUMA (Non-Uniform Memory Access) means not all memory is equally fast for all cores -- memory "close" to one core is slow for another.
The scheduler -- the kernel's version of your team lead -- has to decide: does this task need a P-core or will an E-core do? If two tasks share data, should they be on cores that share the same memory node? Put a latency-sensitive task on the wrong core and it performs like your best engineer assigned to admin work -- technically running, but not where they'd have the most impact.
You have senior engineers (P-cores) and juniors (E-cores). Some tasks need the senior, some are fine for the junior. Some tasks share context (NUMA locality) -- put them on the same person or adjacent people and the handoff cost is low. Put them on opposite sides of the org and context transfer is expensive. The kernel scheduler and the engineering manager are solving the same constrained optimisation problem.
Why this matters outside a textbook
Three domains, three vocabularies, one problem. The structure is identical every time:
When a Gantt chart doesn't feel right, it's worth drawing the other graph. List the tasks. Draw an edge between every pair that can't happen at the same time -- same person, same equipment, same dependency. Look for cliques. That's the minimum.
If you find a 4-clique and you have three engineers, no amount of reshuffling will fix it. You either add a person, cut a task, or accept the slip.
The graph won't lie to you the way the Gantt chart will.
Francis Guthrie was colouring a map with crayons in 1852. He couldn't have known that 124 years later a computer would prove his conjecture, or that 170 years later billions of CPUs would be solving his problem trillions of times per second just to run your code. He definitely couldn't have known that every Monday morning, in every standup in every timezone, someone squinting at a sprint board would be solving it again by instinct.
But they are. And now, so are you -- except you can see the graph. You can find the cliques, count the colours, spot the moment when you've run out of registers and something has to spill. Operations researchers formalised this in the 1940s. Compiler engineers automated it in the 1980s. Managers have been doing it by feel for centuries. The same structure, discovered and rediscovered, because the constraints never change: things that conflict need different slots, and slots are always scarce.