Graph Colouring Calculator

Work out graph colouring instantly with clear inputs, formula shown and shareable results.

About Graph Colouring Calculator

Greedy colouring visits vertices in decreasing degree order and gives each the smallest colour not used by a neighbour. Brooks' theorem guarantees at most Δ colours suffice unless the graph is a complete graph or an odd cycle.

Formula

Greedy bound

χ(G) ≤ Δ + 1, and χ(G) ≤ Δ unless G is complete or an odd cycle

Worked example

With the default values below, Graph Colouring Calculator returns Colours used by greedy colouring of 3. Change any input above and every figure here is recalculated in your browser.

Inputs used

Edges as from,to pairs: 1,2 1,3 2,3 3,4 4,5 1,5
Colours availableaccepts 1–10: 3

Results

Colours used by greedy colouring: 3
Vertex colours: 1:1, 2:3, 3:2, 4:1, 5:2
Maximum degree Δ: 3
Fits your colour budget: Yes, it fits within 3 colours

Step by step

1Values used
2Greedy bound
3Colours used by greedy colouring= 3
4Vertex colours= 1:1, 2:3, 3:2, 4:1, 5:2
5Maximum degree Δ= 3
6Fits your colour budget= Yes, it fits within 3 colours

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

How many colours for the sample graph?

Greedy uses 3, matching the triangle 1-2-3 which forces at least 3.

Is greedy always optimal?

No. It is optimal here but can be off for adversarial vertex orderings; exact chromatic number is NP-hard.