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 the upper bound on χ(G).
This is a heuristic — it gives an upper bound, not always the true minimum.
The Four Color Theorem
Any planar graph (one that can be drawn without edge crossings) needs at most 4 colors. This was proven in 1976 by Appel and Haken — the first major theorem proved with computer assistance.
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.