Graph Coloring Calculator
Assign colors to graph vertices using a greedy algorithm, reporting the chromatic number upper bound.
Inputs
Format: X-Y separated by semicolons
Colors Used (upper bound)
3
Vertex Coloring
A=Red, B=Blue, C=Green, D=Red, E=Blue
Step by step
Values 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
Formula applied
Greedy: for each vertex v in order, assign the smallest color not used by any neighbor of v
Colors Used (upper bound)
= 3
Vertex Coloring
= A=Red, B=Blue, C=Green, D=Red, E=Blue
How it works
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)
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.