Our research involves improved algorithms for graph-coloring, in the context of register allocation. We extend the usual algorithm, first proposed by Chaitin, adding two further routines, one a form of semi-randomized greedy allocation of colors, and the second using local search with random restarts, a method developed in the context of logical satisfiability problems. While time comparisons are hard to make at this point, the extended algorithm can color graphs while spilling significantly less numbers of nodes to memory than does the Chaitin algorithm. Such an algorithm can be extended to the general graph-coloring problem, outside of the particular application considered. In addition, the resulting algorithm makes available adjustable parameters for producing more- or less-optimal executables during compiler runs.