Decomposition tree
The engine runs here, in your browser: the same C++ code as the research engine, compiled to WebAssembly.
About
The chromatic polynomial P(G, k) counts the ways to colour a map with k colours so that no two neighbours share one. This page computes it for any country's map, or for a graph you draw, and shows every step of the computation.
How to read the tree
Radial puts the root at the centre and one ring per level. Tree reads steps from left to right. Arrow keys move between steps.
Computation of the polynomial
For every graph it meets, the engine tries these steps in order, and the first that applies decides that step of the tree.
- No edges. A graph with n vertices and no edges has P = kn.
- Separate components. If the graph falls apart, each component is solved on its own and their polynomials are multiplied.
- Closed forms. Trees, complete graphs, cycles and wheels have known polynomials, so the branch ends there.
- Decompositions. A graph that is a join of independent parts, or that splits along a clique, is solved piece by piece and the pieces' polynomials are combined.
- Cache. If an earlier branch already solved the same graph with its vertices relabelled, the engine recognises it with nauty and reuses that polynomial.
- Delete–contract. Otherwise the edge selector picks an edge e, and P(G) = P(G − e) − P(G / e): the engine solves the graph with the edge deleted and with its ends merged, starting again from step 1 for each, and stores the result in the cache. The learned and MLP selectors were trained to keep the tree small; the others are classic heuristics.
The maps come from the world-graphs dataset. Browse and download them on the Adjacency globe.