Graph Coloring
Color a graph with as few colors as possible
An exhaustive search confirms no proper coloring uses fewer than 3 colors.
- Color 1:1, 3
- Color 2:2, 4
- Color 3:5
No edge joins two vertices of the same color.
About this calculator
The Graph Coloring Calculator finds the chromatic number χ(G) — the fewest colors needed to color a graph's vertices so that no edge joins two vertices of the same color — and shows one optimal coloring. Enter the number of vertices and a list of edges; it computes χ exactly with a branch-and-bound search, reports the maximum degree Δ and the largest clique ω (a lower bound on χ), flags bipartite and complete graphs, and draws the colored graph. Useful for scheduling, register allocation, map coloring, and studying chromatic numbers.
How to color a graph
- Enter the number of vertices; they're numbered 1 to n.
- List the edges as pairs like 1-2, 2-3 — one pair per connection.
- Read the chromatic number χ(G) and the color assigned to each vertex.
- Compare χ with the largest clique ω to see why that many colors are needed, or load a preset to explore.
Common examples
- A triangle (K₃) needs 3 colors — every pair of its vertices is adjacent.
- Even cycles are bipartite and need only 2 colors; odd cycles like C₅ need 3.
- The complete graph Kₙ needs exactly n colors.
- A largest clique of size ω forces at least ω colors, so χ(G) ≥ ω.
- The Grötzsch graph needs 4 colors yet contains no triangle, so χ can exceed the clique number.
Frequently asked questions
What is the chromatic number?
The chromatic number χ(G) is the smallest number of colors needed to color the vertices of a graph so that no edge connects two vertices of the same color.
How is the minimum number of colors found?
Because the graph is small, the calculator searches exactly: it tries 1 color, then 2, and so on, returning the first count for which a proper coloring exists. That count is guaranteed to be the true minimum.
What are the maximum degree and largest clique?
The maximum degree Δ is the most edges meeting at any single vertex. The largest clique ω is the biggest set of vertices that are all mutually adjacent; since they must all differ, χ(G) is at least ω.
Why can a triangle-free graph still need many colors?
A large clique forces many colors, but it isn't the only reason. Odd cycles and graphs like the Grötzsch graph need extra colors even without any triangle, so χ(G) can be larger than the clique number.
Is there a limit on graph size?
Yes. Exact graph coloring is computationally hard, so the calculator caps the graph at 12 vertices to keep results instant and rigorous.