After profiling, graph_get_node_by_id() and graph_update_saturation_degrees() were found to be bottle necks to algorithm performance.  The implementation of these algorithms were improved, and now DSATUR algorithm solves instances with 1000+ nodes and 10000+ edges in < 1000 ms.