Combinatorial Optimization

Graph Coloring

Assign colors to vertices such that no two adjacent vertices share the same color. While finding the minimum colors is NP-Hard, the Greedy Heuristic provides a fast, valid coloring using at most Δ+1 colors.

Greedy TimeO(V + E)

ComplexityNP-Hard

Try Interactive Simulator

Greedy Strategy

Iterate through nodes and assign the smallest available color that doesn't conflict with already-colored neighbors.

Chromatic Number

The minimum number of colors required is χ(G). Greedy coloring is highly sensitive to the order in which nodes are processed.

🖱️ Click to Add • ↔️ Drag to Move • ⌨️ Shift+Drag to Join

Loading Lab...

Combinatorial Optimization

Graph Coloring

Greedy TimeO(V + E)

ComplexityNP-Hard

Try Interactive Simulator

Greedy Strategy

Iterate through nodes and assign the smallest available color that doesn't conflict with already-colored neighbors.

Chromatic Number

The minimum number of colors required is χ(G). Greedy coloring is highly sensitive to the order in which nodes are processed.

🖱️ Click to Add • ↔️ Drag to Move • ⌨️ Shift+Drag to Join