Graph Coloring & Map Coloring Tool
Click nodes to color them and keep every edge joining two different colors. Try a triangle, cycles, a complete graph, a small map, or an exam timetable. The tool flags conflicts, computes the chromatic number χ(G), runs a greedy auto-color, and searches for a proper coloring with k colors.
Controls
Preset graphs
Palette
Clicking a node cycles its color. The selected swatch is used by the set-color action where available.
Graph canvas
Click a node to cycle its color. Edges drawn in red mark a conflict, two adjacent nodes sharing the same color.
Coloring status
Conflicts
0
Chromatic number χ(G)
4
Colors used
0
Nodes colored
0 / 6
Not proper yet. Some nodes are still uncolored.
A proper coloring assigns each node a color so that no edge connects two nodes of the same color. The chromatic number χ(G) is the fewest colors that make this possible. The palette currently offers k = 4 colors.
The same idea drives real scheduling. In exam timetabling, nodes are exams, an edge means a shared student, and colors are time slots, so a proper coloring is a conflict-free schedule. Compilers use it for register allocation, where nodes are variables that are live at the same time and colors are CPU registers. Wireless networks use it for frequency assignment so that nearby transmitters avoid interference.
Reference Guide
Proper graph coloring
A proper coloring assigns a color to every node so that no edge connects two nodes of the same color. The colors are just labels. What matters is that neighbors differ.
Adjacent nodes must take different colors because an edge means a constraint, two things that cannot share the same slot, region, or resource.
The chromatic number
The chromatic number χ(G) is the smallest number of colors that admits a proper coloring. A graph with no edges needs 1 color. Any graph with an edge needs at least 2.
Triangles and odd cycles force 3 colors. A complete graph on n nodes needs n colors because every pair is adjacent.
Greedy and Welsh-Powell
The greedy method visits the nodes one at a time and gives each the smallest color not already used by a neighbor. It always returns a proper coloring.
The Welsh-Powell order visits high-degree nodes first, which often uses fewer colors. Greedy never beats χ(G), so its color count is an upper bound on the true minimum.
The four-color theorem
Any map drawn in the plane can be colored with at most 4 colors so that no two regions sharing a border get the same color. Turn each region into a node and join bordering regions with an edge to get a planar graph.
This means every planar graph satisfies χ(G) ≤ 4. The Map regions preset is one such graph.
Scheduling and timetables
In exam timetabling, nodes are exams and an edge means a student sits both, so they cannot share a time slot. Colors are time slots, and a proper coloring is a conflict-free schedule.
The chromatic number is then the fewest time slots needed. The Exam schedule preset models exactly this situation.
More applications
- Register allocation. Nodes are variables live at the same time, colors are CPU registers, and a coloring keeps clashing values apart.
- Frequency assignment. Nodes are transmitters, edges mean they are close enough to interfere, and colors are frequency bands.
- Sudoku and seating plans. Both reduce to coloring problems where edges encode the rule that two cells or guests must differ.
