Introduction to Compiler Construction in a Java World

270 An Introduction to Compiler Construction in a Java World

1. The first, called the degree < R rule, derives from the fact that a graph with a node

of degree <R (that is a node with <R adjacent nodes) is R-colorable if and only

if the graph with that node removed is R-colorable. We may use this rule to prune

the graph, removing one node of degree <R at a time and pushing it onto a stack;

removing nodes from the graph removes corresponding edges, potentially creating

more nodes with degree <R. We continue removing nodes until either all nodes have

been pruned or until we reach a state where all remaining nodes have degrees ≥ R.

2. The second is called ...