Graph Coloring Calculator
Assign colors to graph vertices using a greedy algorithm, reporting the chromatic number upper bound.
About Graph Coloring Calculator
Graph coloring assigns colors to vertices so that no two adjacent vertices share the same color. The greedy algorithm processes vertices in order and assigns the smallest available color. The result is an upper bound on the chromatic number (minimum colors needed).
Formula
Greedy: for each vertex v in order, assign the smallest color not used by any neighbor of v
- v
- Current vertex
- χ(G)
- Chromatic number (minimum colors needed)
Worked example
With the default values below, Graph Coloring Calculator returns Colors Used (upper bound) of 3. Change any input above and every figure here is recalculated in your browser.
Inputs used
- Vertices (comma separated)
- A, B, C, D, E
- Edges (semicolon separated pairs)
- A-B; A-C; B-C; B-D; C-D; D-E
Results
- Colors Used (upper bound)
- 3
- Vertex Coloring
- A=Red, B=Blue, C=Green, D=Red, E=Blue
Step by step
- 1Values used
- 2Formula applied
- 3Colors Used (upper bound)= 3
- 4Vertex Coloring= A=Red, B=Blue, C=Green, D=Red, E=Blue
Assumptions and limits
- The result is derived only from the 2 inputs listed above. Anything not among them is not part of the calculation.
- In particular, this calculator does not take inflation, tax, fees or charges or compounding frequency into account.
- Figures are rounded for display to whole numbers, so totals built from several rounded parts can differ slightly from the unrounded arithmetic.
How these calculators are built and tested is described on the Methodology page. If a figure looks wrong, please report it.
Frequently Asked Questions
Does greedy always give the minimum number of colors?
No. Greedy gives an upper bound that depends on vertex ordering. The true chromatic number may be lower. Finding the exact chromatic number is NP-hard in general.
What are real-world applications of graph coloring?
Scheduling (exams, tasks), register allocation in compilers, frequency assignment in telecommunications, and map coloring.