Graph Coloring Explorer

The chromatic number χ(G) is the minimum number of colors needed so that no edge joins two same-colored vertices. Finding it exactly is NP-hard — the best general guarantee sits between a clique lower bound (any clique of size k forces at least k colors) and a greedy upper bound (Welsh-Powell coloring by descending degree never uses more than Δ+1 colors, where Δ is the maximum degree). For planar graphs — those drawable without crossing edges — the four color theorem guarantees 4 colors always suffice; it was first proved by computer in 1976 and remains one of the few major theorems requiring exhaustive computer case-checking. Graph coloring underlies real scheduling problems: register allocation in compilers, exam timetabling, and radio frequency assignment all reduce to coloring a conflict graph.

Graph coloring boils down to one rule: no edge may join two vertices of the same color, and you want to get by with as few colors as possible. That single constraint decides everything. A handy test: every cycle of even length can be done with 2 colors, but every cycle of odd length needs 3 — so a triangle (the smallest odd cycle) can never be 2-colored. Build both in the tool and watch the conflict count.

Coloring vertices one at a time, always grabbing the lowest free color, feels safe — but the order you pick matters enormously. On a family called crown graphs — 2n vertices that need only 2 colors — a cruel ordering forces the greedy method to use n colors instead. Its worst case is unbounded, which is exactly why the tool's auto-color sorts vertices by descending degree (Welsh-Powell) to sidestep such traps.