It has been found that the avalanches from an SOC process make effective patterns in a random search for optimal solutions on graphs. An example of such an optimization problem is graph coloring. The SOC process apparently helps the optimization from getting stuck in a local optimum without the use of any annealing scheme, as suggested by previous work on extremal optimization.