—
χ(G) Colors Used
—
Max Degree Δ
—
Edges
—
Valid Coloring
This simulation assigns colours to the vertices of a graph so that no two adjacent vertices share a colour, a problem known as proper vertex colouring. The fewest colours that achieve this is the chromatic number, written χ(G). You can build random Erdős–Rényi graphs or load presets such as the Petersen graph, complete K₅, cycle C₇, bipartite K₃₃ and wheel W₆, then colour them with greedy, Welsh–Powell or DSatur ordering.
The sidebar lets you set the node count (5–20), the edge probability p (0.1–0.7) for random graphs, and the colouring algorithm. "Color!" runs the chosen heuristic at once, while "Step-by-Step" advances one vertex at a time so you can watch the order and the smallest available colour being chosen. The live panel reports colours used, maximum degree Δ, edge count and whether the colouring is conflict-free. Graph colouring underpins exam timetabling, register allocation in compilers and radio-frequency assignment.
What is the chromatic number?
The chromatic number χ(G) is the smallest number of colours needed to colour every vertex so that no edge joins two vertices of the same colour. The simulator displays the colours actually used by the chosen heuristic, which equals χ(G) when the heuristic is optimal but may overshoot it otherwise.
How does the greedy algorithm colour a graph?
Greedy colouring visits the vertices in a fixed order and gives each one the lowest-numbered colour not already used by its neighbours. It is fast and always produces a valid colouring, but the number of colours it needs depends heavily on the vertex ordering.
What do the node and edge probability sliders do?
The node slider sets how many vertices a random graph has, from 5 to 20. The edge probability p, between 0.1 and 0.7, is the chance that any given pair of vertices is joined by an edge, following the Erdős–Rényi G(n,p) model. Higher p means denser graphs that usually need more colours.
Welsh–Powell is greedy colouring applied to vertices sorted in decreasing order of degree, so high-degree vertices are coloured first. This ordering often reduces the number of colours compared with an arbitrary sequence, and it guarantees a colouring using at most one more than the maximum degree.
DSatur, short for degree of saturation, repeatedly colours the uncoloured vertex with the most distinct colours already present among its neighbours, breaking ties by highest degree. It adapts the order dynamically as colours are placed and tends to find near-optimal colourings, exactly colouring all bipartite graphs.
Not necessarily. Greedy, Welsh–Powell and DSatur are heuristics, so they may use more colours than the minimum. Finding the exact chromatic number is NP-hard in general, so for arbitrary graphs these methods give good, fast answers rather than a guaranteed optimum.
A bipartite graph such as K₃₃ splits its vertices into two groups with edges only running between groups. Because no edge lies inside a group, you can colour one group with colour one and the other with colour two, giving a chromatic number of exactly two for any graph with no odd cycle.
The four-colour theorem states that any planar graph, one drawable without crossing edges, can be coloured with at most four colours. It maps onto colouring countries on a map so neighbours differ, and was the first major theorem proved with substantial help from a computer in 1976.
The maximum degree Δ is the largest number of edges meeting at any single vertex. Greedy colouring never needs more than Δ + 1 colours, and Brooks' theorem sharpens this to Δ colours for connected graphs that are neither complete nor odd cycles.
Vertices can represent exams, processor registers, transmitter frequencies or workers, with edges marking conflicts that must differ. Colouring then schedules exams without clashes, allocates registers without overwriting, assigns interference-free frequencies and packs tasks into the fewest time slots, mirroring the colours shown here.