Graph Coloring (Greedy)
Software Engineer path · lesson 30 of 99Assign colors to vertices such that no two adjacent vertices share the same color. The greedy approach gives an upper bound on the chromatic number.
Undirected, like A-B. Badges name each node's colour (c1–c4).
Try 2 on Odd cycle: no 2-colouring exists, and you can watch the search prove it.
Colour 6 nodes with 3 colours so no edge joins two nodes of the same colour.
- 1solve(i): # colour nodes in order
- 2 if i == n: return true
- 3 for c in 1..k:
- 4 if no neighbour of node[i] has colour c:
- 5 colour[node[i]] = c; if solve(i + 1): return true
- 6 colour[node[i]] = none # backtrack
- 7 return false
- Tries
- 0 / 12
- Backtracks
- 0 / 0
Tap any element in the diagram to inspect its state at this step.
Keys: ← → step, Space play/pause. Predict mode pauses before key steps and asks what happens next.
Greedy colouring
Order the steps of the greedy colouring algorithm.
Tap a piece, then tap where it goes — or drag it. Tap the tray to take one back.
- 1Drop a step here
- 2Drop a step here
- 3Drop a step here
- 4Drop a step here
- 5Drop a step here
Test your knowledge
What is the chromatic number of a graph?
The short version
Think of scheduling exams. No two exams can happen simultaneously if they share students. Assigning time slots is like coloring: adjacent nodes (shared students) need different colors (times).
In more depth
Greedy Coloring Algorithm
Properties
Applications
When to reach for this
- Assign labels with adjacency constraints
- Scheduling with conflicts
- Partitioning into independent sets
- Keywords: 'no two adjacent', 'bipartite', 'conflict'
Interview Questions
References & Further Reading
Love this visualization?
Sign up to track your progress, earn achievements, use the AI assistant, and access your personal learning dashboard.
100% free • No credit card required