Graph Chromatic Number Estimator
Estimate the chromatic number of a graph using the Welsh-Powell greedy coloring algorithm.
Enter edges and find the minimum colors needed.
Graph Coloring
Graph coloring assigns a color to each vertex so that no two adjacent vertices share the same color. The chromatic number χ(G) is the minimum number of colors needed.
Welsh-Powell Algorithm
This greedy algorithm finds a good (not always optimal) upper bound:
- List all vertices sorted by degree, highest degree first.
- Assign the first color to the first vertex.
- For each remaining vertex, assign the lowest color not used by any neighbor.
- The number of distinct colors used is an upper bound on χ(G).
This is a heuristic. It gives an upper bound, not always the true minimum. Sorting by degree first is what makes it a decent one: the awkward, heavily connected vertices get coloured while there is still freedom, and the loosely connected ones fill in afterwards.
Finding χ(G) exactly is NP-hard, which is the whole reason a heuristic is used. For small graphs you could brute-force it; past a few dozen vertices you cannot, and a good upper bound is what you get instead.
Bounds worth knowing
Any greedy colouring uses at most Δ+1 colours, where Δ is the highest degree, because a vertex has at most Δ neighbours and one of the first Δ+1 colours must therefore be free. Brooks’ theorem sharpens that to Δ for every connected graph except two cases: complete graphs and odd cycles, which genuinely need Δ+1. From below, a set of k vertices all joined to each other forces at least k colours. The calculator reports both a floor and a ceiling, and when they meet you have the exact answer rather than an estimate.
The Four Color Theorem
Any planar graph (one that can be drawn without edge crossings) needs at most 4 colors. Appel and Haken proved it in 1976, the first major theorem to be settled with computer assistance, and the proof was controversial for exactly that reason: no human can check the 1,834 cases it reduces to by hand.
Common Chromatic Numbers
| Graph Type | χ(G) |
|---|---|
| Empty graph (no edges) | 1 |
| Bipartite graph | 2 |
| Odd cycle (C₅, C₇, …) | 3 |
| Complete graph Kₙ | n |
| Petersen graph | 3 |
Real-World Applications
- Scheduling: assign exam time slots so no student has two exams at the same time
- Register allocation: assign CPU registers to variables in compiler design
- Map coloring: color countries so no bordering countries share a color
- Frequency assignment: assign radio frequencies so nearby towers don’t interfere
Enter your graph edges below (e.g. “1-2, 1-3, 2-3, 3-4”) and see the greedy coloring result.
How we build and check this calculator
This calculator runs entirely in your browser, so the numbers you enter stay on your device. The math behind it is written by hand and tested against worked examples and standard references before the page goes live.
SuperGlobalCalculator is independently built and maintained. See how we build and verify our calculators.