Graph Coloring Calculator
Find the exact chromatic number of a graph of up to twelve nodes by testing every colouring, and print one valid colouring beside the greedy upper bound.
Graph Coloring Calculator
Find the exact chromatic number of a graph of up to twelve nodes by testing every colouring, and print one valid colouring beside the greedy upper bound.
How this page computes
The adjacency map comes from the edge list. For each candidate colour count from one upward, a recursive assignment places nodes in order, rejecting a colour a neighbour already has.
The first count that completes is the chromatic number. A greedy pass then colours the nodes in order for comparison, and both results are printed with the edges they respect.
The calculation runs entirely in this browser tab; nothing is uploaded.
The page finds the fewest colours that colour a graph so that no edge joins two nodes of the same colour. A triangle needs 3; a four-node cycle needs 2, because opposite corners can share.
The number is exact: the page tries every colouring with one colour, then two, and stops at the first count that works. That is why it refuses above twelve nodes — the trial is exponential, and a greedy colouring would be an upper bound, not the chromatic number.
How to use Graph Coloring Calculator
Type the edges one per line and press Run. The graph is read as undirected, because a colouring constraint has no direction.
The output gives the chromatic number, one colouring grouped by colour, and the greedy upper bound for comparison. When the two differ, the gap is exactly the cost of a greedy choice.
Why trying every k-colouring decides the number
A graph is k-colourable if its nodes can be assigned one of k colours with no edge inside a colour class. The page tests k = 1, 2, 3, … and for each k runs a backtracking assignment in node order. The first k that succeeds is the chromatic number, because every smaller k failed.
A greedy colouring is also computed: walk the nodes and give each the smallest colour none of its neighbours has. That never uses fewer colours than necessary but can use more, and printing both makes the difference visible rather than theoretical.
What to Expect
Best for
- The exact chromatic number of a graph up to twelve nodes
- A register-allocation or scheduling toy example
- Seeing where a greedy colouring wastes a colour
Not ideal for
- Large graphs, where exact colouring is impractical
- Planar four-colour proofs, which this page does not attempt
- Directed graphs, where the constraint is different
What this tool keeps
- Every edge; a repeated pair is one constraint
What may need cleanup
- Nothing: the number and the colouring are final
Common errors
- A self-loop makes the graph uncolourable, and the search refuses with the reason
- More than twelve nodes is refused with the ceiling named
Example use cases
- Colour a triangle and confirm it needs three colours
- Show that a four-node cycle needs only two
- Compare an exact number with a greedy bound
Sample input
edges A-B, B-C, C-A (a triangle)
Sample output
chromatic number 3, colouring A=1, B=2, C=3
Who this is for
- Students meeting graph colouring
- Readers checking a scheduling bound
Frequently asked questions
Why does a triangle need three colours?
Because every pair of its nodes is joined by an edge, so no two can share a colour. A graph with a clique of size k needs at least k colours, and for the triangle that bound is also achieved.
Can a greedy colouring use more colours than necessary?
Yes. On a path of four nodes it may use three where two suffice, depending on the node order. The page prints both numbers so the waste is visible.
What does a self-loop do?
It makes colouring impossible, because a node would have to differ from itself. The page refuses instead of returning a number that no assignment achieves.
Build custom tools for your store
Join the SDK program to create useful ecommerce utilities for your store.