Barry,
Your algorithm is the classic CS algorithm. My algorithms exploits the (low dimensional) geometric nature of our graphs. Assuming you have a decent partitioning, as Jed says, you have, for instance, "interior" vertices that have no external dependence so coloring them is silly. The algorithm enforces only the (external) data dependencies that are required for correctness, which for normal PDE problems results in a far shorter dependency depth than generic coloring and leaves you some freedom to reorder for performance.
