← Lab · Chapter: Vertex coloring: the DSATUR branch-and-bound

Vertex coloring: the DSATUR branch-and-bound

The tree of the partial colorings node by node: most saturated vertex, one child per feasible color plus one new color, pruning when q ≥ UB. ◀ ▶ one step at a time, «Run» to watch them all (choose the speed); the «Instance» menu and «Edit…» change the instance.