DSatur Graph Coloring
Same crown graph, smarter vertex ordering →
optimal 2 colors
partition 1
partition 2
A
C
E
B
D
F
sat: 0
sat: 0
sat: 0
sat: 0
sat: 0
sat: 0
▲ picked
▼ picked
▲ picked
▼ picked
▲ picked
▼ picked
← Back
▶ Play
Next →
↺
Press
Play
or
Next →
to watch DSatur pick the
smartest
vertex at each step.
Uncolored
Red
Blue
sat: n
Saturation degree
Being checked
Greedy: 3 colors 😬
vs
DSatur: 2 colors ✓ optimal