MIra este link que habla de un algoritmo con coloración de grafos, no parece difícil de programar en php
http://www.programacion.com/articulo/grafos_asignacion/
también te puedes descagar un programa para probarlo, pero la dinámica del algoritmo está clara.