Graph Coloring Solver

Visualize and solve graph coloring problems using greedy algorithms

How to use:

Graph Presets

Graph Controls

Algorithm

800ms
Add Vertices

Vertices

0

Edges

0

Chromatic Number

-

Max Degree

0
About Graph Coloring Algorithms

Greedy (Sequential) Coloring

Colors vertices one by one, assigning the smallest color number not used by adjacent vertices. Simple but may not always find the optimal solution.

Welsh-Powell Algorithm

Orders vertices by degree (highest first), then applies greedy coloring. Often produces better results than simple greedy.

DSatur (Degree of Saturation)

Colors vertices by choosing the one with the highest saturation degree (most different colors in neighbors). Typically produces near-optimal colorings.

Chromatic Number

The minimum number of colors needed to properly color a graph. For some graphs:

  • Bipartite graphs: χ ≤ 2
  • Complete graph Kn: χ = n
  • Cycle Cn: χ = 2 (even n) or 3 (odd n)