MathCastle
Graph TheoryEasyGraph Coloring

Graph Coloring · Easy problem

A compiler must assign registers to five live variables v,w1,w2,w3,w4v, w_1, w_2, w_3, w_4. Variable vv is live for the whole routine, so it interferes with all four wiw_i. The wiw_i are only live in a shifting window, so each interferes only with its immediate neighbor: w1&w2w_1\&w_2, w2&w3w_2\&w_3, w3&w4w_3\&w_4. Two interfering variables cannot share a register. What is the fewest registers needed?